首页 > 代码库 > 学习笔记::矩阵树定理

学习笔记::矩阵树定理

我很懒惰,没有理解

是这样做的

先计算每个点的度数

a[i][j]=i到j边数*-1

进行高斯消元

最后把对角线乘起来就是答案

技术分享
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-9
#define N 20
int n,m;
int d[N][N],c[N][N];
double a[N][N];
void gauss()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n+1;j++)
        {
            if(j==n+1)
            {
                printf("0\n");
                return;
            }
            if(fabs(a[j][i])>eps)
            {
                for(int k=i;k<=n;k++) swap(a[j][k],a[i][k]);
                break;
            }
        }
        for(int j=i+1;j<=n;j++)
        {
            double t=a[j][i]/a[i][i];
            for(int k=1;k<=n;k++) a[j][k]=a[j][k]-t*a[i][k];
        }
    }
    double ans=1;
    for(int i=1;i<=n;i++) ans*=a[i][i];
    printf("%.0lf\n",abs(ans));
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(d,0,sizeof(d));
        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        scanf("%d%d",&n,&m);
        n--;
        for(int i=1;i<=m;i++)
        {
            int u,v; scanf("%d%d",&u,&v);
            d[u][u]++; d[v][v]++;
            c[u][v]++; c[v][u]++;
        }
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++) a[i][j]=d[i][j]-c[i][j];
        gauss();
    }
    return 0;
}
View Code

 

学习笔记::矩阵树定理