「SPOJ-P104」Highways(生成树计数)

发表于 | 分类于 ，

「SPOJ-P104」Highways
Matrix-Tree定理，求生成树的个数

题意

一个有n座城市的组成国家，城市1至n编号，其中一些城市之间可以修建高速公路，需要有选择的修建一些高速公路，从而组成一个交通网络。计算有多少种方案，使得任意两座城市之间恰好只有一条路径。

思路

定义

1、图G的度数矩阵$D[G]$，满足当$i≠j$ 时,$d_{ij}=0$；当$i=j$时，$d_{ij}$ 等于$vi$ 的度数。

2、图G的邻接矩阵$A[G]$

定义图G的基尔霍夫矩阵$C[G]=D[G]-A[G]$有如下性质：

①对于任意一个图,他的基尔霍夫矩阵C的行列式的值为0.

②如果图G不连通,其基尔霍夫矩阵的任意主子式行列式值为0.

③若图G是一棵树,则C[G]的任意一个n-1阶主子式的行列式的值为1.

Matrix-Tree定理

定义$G $的所有不同的生成树的个数等于其Kirchhoff矩阵$C[G]$任何一个$n-1 $阶主子式的行列式的绝对值。所谓$n-1$ 阶主子式，就是对于$r(1≤r≤n)$，将$C[G]$的第$r$ 行、第$r $列同时去掉后得到的新矩阵，用$Cr[G]$表示。

参考

Kirchhoff’s theorem
2007年国家集训队论文 周冬《生成树的计数及其应用》

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

long long C[15][15];

long long det(int n)
{
    long long ret=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
            while(C[j][i])
            {
                long long t=C[i][i]/C[j][i];
                for(int k=i;k<=n;k++)
                    C[i][k]=(C[i][k]-C[j][k]*t);
                for(int k=i;k<=n;k++)
                    swap(C[i][k],C[j][k]);
                ret=-ret;
            }
        if(!C[i][i])
            return 0;
        ret=ret*C[i][i];
    }
    return ret>0?ret:-ret;
}

int main()
{
    int t,n,m,u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(C,0,sizeof C);
        while(m--)
        {
            scanf("%d%d",&u,&v);
            C[u][u]++;C[v][v]++;
            C[u][v]--;C[v][u]--;
        }
        printf("%lld\n",det(n));
    }
    return 0;
}