over 4 years ago

颓太多了嗷嗷嗷嗷嗷嗷嗷!!!还没有理解这玩意
做法步骤:
1、基尔霍夫矩阵:度数矩阵-邻接矩阵
2、计算n-1的子矩阵的行列式
方法:①类似高斯消元,处理出上三角,将对角线乘起来。取绝对值
②排列公式 详见bzoj1494
待完善:
行列式的性质
生成树计数 证明 其他定理 特殊性质

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define maxn 20

#define eps 1e-7

using namespace std;
double a[maxn][maxn];
int d[maxn];
int n,m;
double fabs(double x)
{
    if(x<0) return -x;else return x; 
}
bool zero(double x)
{
    if (fabs(x)<eps) return true;return false;
}
void calc()
{
    int i,j,k;double result=1;
    for (i=1;i<n;i++)
      {
        for (j=i;j<n;j++)
         if (!zero(a[j][i]))break;
        if (j>=n) {result=0;break;}
        if (j!=i)
        {
             result=result*-1;
             for (k=i;k<n;k++) swap(a[i][k],a[j][k]);
        }
        for (j=i+1;j<n;j++)
        if (!zero(a[j][i]))
          {
            for (k=i+1;k<n;k++)
                a[j][k]-=a[j][i]/a[i][i]*a[i][k];
          }
        result=result*a[i][i];
      }
    if (result<0) result=-result;
    printf("%lld\n",(long long )(result+0.5));
}
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') c=getchar(),bj=-1;
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
int main()
{
    int x,y,z,i,j,k;
    int t=readln();
    for (;t--;)
    {
    n=readln();m=readln();
    memset(a,0,sizeof(a));
    memset(d,0,sizeof(d));
    for (i=1;i<=m;i++)
    {
        x=readln();y=readln();
        a[x][y]--;a[y][x]--;
        d[x]++;d[y]++;
    }
    for (i=1;i<=n;i++) a[i][i]=d[i];
    calc(); 
    }
}
← 【bzoj1977】次小生成树 【bzoj2395】【Balkan 2011】【最小乘积生成树】Timeismoney →
 
comments powered by Disqus