首页 > 其他 > 详细

生成树记数 Matrix-Tree定理

时间:2014-02-17 15:25:19      阅读:345      评论:0      收藏:0      [点我收藏+]

  这个问题就是最经典的生成树记数问题,题目为spoj p104 highway。

  首先我们引入Matrix-Tree定理,由kirchhoff证明,定理的概述为,对于图G,我们定义若干个矩阵,

    D[G],Dij=(i!=j)?0:vi;这里vi为节点i的度数。

    A[G],Aij=存在边(u,v),即A为图G的连通01矩阵。

    定义Kirchhoff Matrix C[G]=D[G]-A[G],那么C[G]的任意一个n-1阶主子式的行列式的绝对值为图G生成树个数。

这样这个问题就可以比较容易的解决了,行列式的求法为将矩阵用类似于消元的方法消成上三角矩阵(其实我也是记住的代码= =)。

bubuko.com,布布扣
//By BLADEVIL
#include <cstdio>
#include <cstring>
#define maxn 20

using namespace std;

int a[maxn][maxn];
double g[maxn][maxn];

bool zero(double x)
{
    return (((x<0)?-x:x)<1e-15);
}

void swap(double &a,double &b)
{double c=a;a=b;b=c;}

double delte(double a[maxn][maxn],int n)
{
    int sign=0;
    double ans=1;
    for (int i=1;i<=n;i++)
    {
        if (zero(a[i][i]))
        {
            int j;
            for (j=i+1;(j<=n)&&(zero(a[j][i]));j++);
            if (j>n) return 0;
            for (int k=i+1;k<=n;k++) swap(a[i][k],a[j][k]);
            sign++;
        }
        ans*=a[i][i];
        for (int j=i+1;j<=n;j++) a[i][j]/=a[i][i];
        for (int j=i+1;j<=n;j++)
            for (int k=i+1;k<=n;k++)
                a[j][k]-=a[i][j]*a[k][i];
    }
    if (sign&1) ans=-ans;
    return ans;
}

void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(g,0,sizeof g); memset(a,0,sizeof a);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=1;
        g[x][x]++; g[y][y]++;
    }
    n--;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (a[i][j]) g[i][j]=-1;
    printf("%.0f\n",delte(g,n));
}

int main()
{
    int task;
    scanf("%d",&task);
    while (task--) solve();
    return 0;
}
bubuko.com,布布扣

生成树记数 Matrix-Tree定理

原文:http://www.cnblogs.com/BLADEVIL/p/3551923.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!