生成树计数

生成树计数就是统计一张图中一共有多少种构造生成树的方案。

大概要用到组合数学等等的数学知识。

以下内容均来自NOI2007国家集训队论文 周冬 《生成树的计数及其应用》:

-------------------------

Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前,我们首先明确几个概念:

1、G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当ij时,dij=0;当i=j时,dij等于vi的度数。

2、G的邻接矩阵A[G]也是一个n*n的矩阵, 并且满足:如果vivj之间有边直接相连,则aij=1,否则为0。

我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:

G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。

所谓n-1阶主子式,就是对于r(1≤rn),将C[G]的第r行、第r列同时去掉后得到的新矩阵,用Cr[G]表示。

在证明Matrix-Tree定理的过程中,我们使用了无向图G的关联矩阵BB是一个nm列的矩阵,行对应点而列对应边。B满足,如果存在一条边e={vi,vj},那在e所对应的列中,vivj所对应的那两行,一个为1、另一个为-1,其他的均为0。至于谁是1谁是-1并不重要。

接下来,我们考察BBT。容易证明,(BBT)ij等于B的第i行与第j列的点积。所以,当i=j时,(BBT)ij等于与vi相连的边的个数,即vi的度数;而当ij时,如果有一条连接vivj的边,则(BBT)ij等于-1,否则等于0。这与Kirchhoff矩阵的定义完全相同!因此,我们得出:C=BBT!也就是说,我们可以将C的问题转化到BBT上来。

-------------------------

这里没办法帖公式,只好省去详细的证明过程了,详见论文原文吧:http://files.cnblogs.com/jcf94/Counting_Spanning_Tree.rar

-------------------------

例题有:

SPOJ P104 Highways

题目就是裸的生成树计数,用Matrix_Tree定理可以直接解出。

然后贴一个Kuang神的模板:

 1 /* ***********************************************
 2 MYID    : Chen Fan
 3 LANG    : G++
 4 PROG    : Count_Spaning_Tree_From_Kuangbin
 5 ************************************************ */
 6
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <algorithm>
10 #include <iostream>
11 #include <math.h>
12
13 using namespace std;
14 const double eps = 1e-8;
15 const int MAXN = 110;
16
17 int sgn(double x)
18 {
19     if(fabs(x) < eps)return 0;
20     if(x < 0)return -1;
21     else return 1;
22 }
23
24 double b[MAXN][MAXN];
25 double det(double a[][MAXN],int n)
26 {
27     int i, j, k, sign = 0;
28     double ret = 1;
29     for(i = 0;i < n;i++)
30     for(j = 0;j < n;j++) b[i][j] = a[i][j];
31     for(i = 0;i < n;i++)
32     {
33         if(sgn(b[i][i]) == 0)
34         {
35             for(j = i + 1; j < n;j++)
36             if(sgn(b[j][i]) != 0) break;
37             if(j == n)return 0;
38             for(k = i;k < n;k++) swap(b[i][k],b[j][k]);
39             sign++;
40         }
41         ret *= b[i][i];
42         for(k = i + 1;k < n;k++) b[i][k]/=b[i][i];
43
44         for(j = i+1;j < n;j++)
45         for(k = i+1;k < n;k++) b[j][k] -= b[j][i]*b[i][k];
46     }
47     if(sign & 1)ret = -ret;
48     return ret;
49 }
50
51 double a[MAXN][MAXN];
52 int g[MAXN][MAXN];
53
54 int main()
55 {
56     int T;
57     int n,m;
58     int u,v;
59     scanf("%d",&T);
60     while(T--)
61     {
62         scanf("%d%d",&n,&m);
63         memset(g,0,sizeof(g));
64         while(m--)
65         {
66             scanf("%d%d",&u,&v);
67             u--;v--;
68             g[u][v] = g[v][u] = 1;
69         }
70         memset(a,0,sizeof(a));
71         for(int i = 0;i < n;i++)
72         for(int j = 0;j < n;j++)
73         if(i != j && g[i][j])
74         {
75             a[i][i]++;
76             a[i][j] = -1;
77         }
78         double ans = det(a,n-1);
79         printf("%.0lf\n",ans);
80     }
81     return 0;
82 }

最小生成树计数:

在ACM2012金华赛区的网赛中曾经出现过这么一道题,现在是HDU 4408,统计最小生成树的个数。

方法是Kruskal+Matrix_Tree定理,也就是把上面的算法加上Kruskal:

来自:http://blog.csdn.net/jarily/article/details/8902402 的算法解释:

  • *算法引入:
  • *给定一个含有N个结点M条边的无向图,求它最小生成树的个数t(G);
  • *
  • *算法思想:
  • *抛开“最小”的限制不看,如果只要求求出所有生成树的个数,是可以利用Matrix-Tree定理解决的;
  • *Matrix-Tree定理此定理利用图的Kirchhoff矩阵,可以在O(N3)时间内求出生成树的个数;
  • *
  • *kruskal算法:
  • *将图G={V,E}中的所有边按照长度由小到大进行排序,等长的边可以按照任意顺序;
  • *初始化图G’为{V,Ø},从前向后扫描排序后的边,如果扫描到的边e在G’中连接了两个相异的连通块,则将它插入G’中;
  • *最后得到的图G’就是图G的最小生成树;
  • *
  • *由于kruskal按照任意顺序对等长的边进行排序,则应该将所有长度为L0的边的处理当作一个阶段来整体看待;
  • *令kruskal处理完这一个阶段后得到的图为G0,如果按照不同的顺序对等长的边进行排序,得到的G0也是不同;
  • *虽然G0可以随排序方式的不同而不同,但它们的连通性都是一样的,都和F0的连通性相同(F0表示插入所有长度为L0的边后形成的图);
  • *
  • *在kruskal算法中的任意时刻,并不需要关注G’的具体形态,而只要关注各个点的连通性如何(一般是用并查集表示);
  • *所以只要在扫描进行完第一阶段后点的连通性和F0相同,且是通过最小代价到达这一状态的,接下去都能找到最小生成树;
  • *
  • *经过上面的分析,可以看出第一个阶段和后面的工作是完全独立的;
  • *第一阶段需要完成的任务是使G0的连通性和F0一样,且只能使用最小的代价;
  • *计算出这一阶段的方案数,再乘上完成后续事情的方案数,就是最终答案;
  • *
  • *由于在第一个阶段中,选出的边数是一定的,所有边的长又都为L0;
  • *所以无论第一个阶段如何进行代价都是一样的,那么只需要计算方案数就行了;
  • *此时Matrix-Tree定理就可以派上用场了,只需对F0中的每一个连通块求生成树个数再相乘即可;

同样,贴一个bin神模板:

  1 /* ***********************************************
  2 MYID    : Chen Fan
  3 LANG    : G++
  4 PROG    : Counting_MST_From_Kuangbin_HDU4408
  5 ************************************************ */
  6
  7 #include <map>
  8 #include <stack>
  9 #include <queue>
 10 #include <math.h>
 11 #include <vector>
 12 #include <string>
 13 #include <stdio.h>
 14 #include <string.h>
 15 #include <stdlib.h>
 16 #include <iostream>
 17 #include <algorithm>
 18 #define N 405
 19 #define M 4005
 20 #define E
 21 #define inf 0x3f3f3f3f
 22 #define dinf 1e10
 23 #define linf (LL)1<<60
 24 #define LL long long
 25 #define clr(a,b) memset(a,b,sizeof(a))
 26 using namespace std;
 27
 28 LL mod;
 29 struct Edge
 30 {
 31     int a,b,c;
 32     bool operator<(const Edge & t)const
 33     {
 34         return c<t.c;
 35     }
 36 }edge[M];
 37 int n,m;
 38 LL ans;
 39 int fa[N],ka[N],vis[N];
 40 LL gk[N][N],tmp[N][N];
 41 vector<int>gra[N];
 42
 43 int findfa(int a,int b[]){return a==b[a]?a:b[a]=findfa(b[a],b);}
 44
 45 LL det(LL a[][N],int n)
 46 {
 47     for(int i=0;i<n;i++)for(int j=0;j<n;j++)a[i][j]%=mod;
 48     long long ret=1;
 49     for(int i=1;i<n;i++)
 50     {
 51         for(int j=i+1;j<n;j++)
 52             while(a[j][i])
 53             {
 54                 LL t=a[i][i]/a[j][i];
 55                 for(int k=i;k<n;k++)
 56                     a[i][k]=(a[i][k]-a[j][k]*t)%mod;
 57                 for(int k=i;k<n;k++)
 58                     swap(a[i][k],a[j][k]);
 59                 ret=-ret;
 60             }
 61         if(a[i][i]==0)return 0;
 62         ret=ret*a[i][i]%mod;
 63         //ret%=mod;
 64     }
 65     return (ret+mod)%mod;
 66 }
 67
 68 int main()
 69 {
 70     while(scanf("%d%d%I64d",&n,&m,&mod)==3)
 71     {
 72
 73         if(n==0 && m==0 && mod==0)break;
 74
 75         memset(gk,0,sizeof(gk));
 76         memset(tmp,0,sizeof(tmp));
 77         memset(fa,0,sizeof(fa));
 78         memset(ka,0,sizeof(ka));
 79         memset(tmp,0,sizeof(tmp));
 80
 81         for(int i=0;i<N;i++)gra[i].clear();
 82         for(int i=0;i<m;i++)
 83             scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
 84         sort(edge,edge+m);
 85         for(int i=1;i<=n;i++)fa[i]=i,vis[i]=0;
 86         int pre=-1;
 87         ans=1;
 88         for(int h=0;h<=m;h++)
 89         {
 90             if(edge[h].c!=pre||h==m)
 91             {
 92                 for(int i=1;i<=n;i++)
 93                     if(vis[i])
 94                     {
 95                         int u=findfa(i,ka);
 96                         gra[u].push_back(i);
 97                         vis[i]=0;
 98                     }
 99                 for(int i=1;i<=n;i++)
100                     if(gra[i].size()>1)
101                     {
102                         for(int a=1;a<=n;a++)
103                             for(int b=1;b<=n;b++)
104                                 tmp[a][b]=0;
105                         int len=gra[i].size();
106                         for(int a=0;a<len;a++)
107                             for(int b=a+1;b<len;b++)
108                             {
109                                 int la=gra[i][a],lb=gra[i][b];
110                                 tmp[a][b]=(tmp[b][a]-=gk[la][lb]);
111                                 tmp[a][a]+=gk[la][lb];tmp[b][b]+=gk[la][lb];
112                             }
113                         long long ret=(long long)det(tmp,len);
114                         ret%=mod;
115                         ans=(ans*ret%mod)%mod;
116                         for(int a=0;a<len;a++)fa[gra[i][a]]=i;
117                     }
118                 for(int i=1;i<=n;i++)
119                 {
120                     ka[i]=fa[i]=findfa(i,fa);
121                     gra[i].clear();
122                 }
123                 if(h==m)break;
124                 pre=edge[h].c;
125             }
126             int a=edge[h].a,b=edge[h].b;
127             int pa=findfa(a,fa),pb=findfa(b,fa);
128             if(pa==pb)continue;
129             vis[pa]=vis[pb]=1;
130             ka[findfa(pa,ka)]=findfa(pb,ka);
131             gk[pa][pb]++;gk[pb][pa]++;
132         }
133         int flag=0;
134         for(int i=2;i<=n&&!flag;i++)if(ka[i]!=ka[i-1])flag=1;
135         ans%=mod;
136         printf("%I64d\n",flag?0:ans);
137     }
138     return 0;
139 }

然后,最后这一题:

HDU4305

综合性相当强的一题:

首先需要用计算几何的知识对平面上的点构图,形成图之后用Matrix-Tree定理求解生成树的个数。

但是题目数据比较大,对行列式求值的时候,需要用到高斯消元求上三角阵,行列式的值等于对角线元素的积。
由于是整数然后再mod。消元时需要求最小公倍数。还需要拓展欧几里得算法求逆元。

日后等有人能集我们队三者之大成之后,应该就可以挑战这道题了。

时间: 10-31

生成树计数的相关文章

bzoj1002 生成树计数 找规律

这道题第一眼是生成树计数,n是100,是可以用O(n^3)的求基尔霍夫矩阵的n-1阶的子矩阵的行列式求解的,但是题目中并没有说取模之类的话,就不好办了. 用高精度?有分数出现. 用辗转相除的思想,让它不出现分数.但过程中会出现负数,高精度处理负数太麻烦. 用Python打表?好吧,Python还不熟,写不出来..... 所以,如果这道题我考场上遇到,最多用double骗到n<=20的情况的部分分. 最终只能求助于题解了... 好像是通过观察行列式的特点,推导出关于答案f(n)的递推式(f(n)=

kuangbin带你飞 生成树专题 : 次小生成树; 最小树形图;生成树计数

第一个部分 前4题 次小生成树 算法:首先如果生成了最小生成树,那么这些树上的所有的边都进行标记.标记为树边. 接下来进行枚举,枚举任意一条不在MST上的边,如果加入这条边,那么肯定会在这棵树上形成一个环,如果还要维护处树的特点 那么就要在这个环上删去一条边,这样他还是树,删掉的边显然是这条链上权值最大边更可能形成次小生成树.那么就有2中方法可以做. 第一种PRIM在prim时候直接可以做出这个从I到J的链上权值最大的值MAX[i][j]; 同时可以用kruskal同样方式标记树边,然后DFS跑

Uva 10766 Organising the Organisation (Matrix_tree 生成树计数)

题目描述: 一个由n个部门组成的公司现在需要分层,但是由于员工间的一些小小矛盾,使得他们并不愿意做上下级,问在满足他们要求以后有多少种分层的方案数? 解题思路: 生成树计数模板题,建立Kirchhoff矩阵,利用Matrix_tree定理求解. Kirchhoff矩阵:假设G为n*n矩阵,C为G的入度矩阵(i==j时,C[i][j]等于i的入度;i!=j时,C[i][j]等于零),A为G的邻接矩阵,那么就有Kirchhoff矩阵等于C-A. Matrix_tree定理:G的不同生成树的个数等于其

SPOJ104 Highways,生成树计数

高速公路(SPOJ104 Highways) 一个有n座城市的组成国家,城市1至n编号,其中一些城市之间可以修建高速公路.现在,需要有选择的修建一些高速公路,从而组成一个交通网络.你的任务是计算有多少种方案,使得任意两座城市之间恰好只有一条路径? 数据规模:1≤n≤12. 生成树计数 算法步骤: 1. 构建拉普拉斯矩阵 Matrix[i][j] = degree(i) , i==j -1,i-j有边 0,其他情况 2. 去掉第r行,第r列(r任意) 3. 计算矩阵的行列式 #include <m

bzoj 1005: [HNOI2008]明明的烦恼 prufer编号&amp;&amp;生成树计数

1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 2248  Solved: 898[Submit][Status] Description 自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? Input 第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度

生成树计数模板

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=55; typedef long long LL; int D[N][N]; LL C[N][N];//Kirchhoff矩阵 LL Det(LL a[][N],int n)//生成树计数:Matrix-

【生成树计数】专题总结

在CTSC和APIO上好像经常听到生成树计数这东西 于是就去看了下论文 蒟蒻表示看不懂证n明orz 反正懂用就行了.. 生成树计数 生成树计数就是给出一种n个点的无向图G 求这n个点的生成树个数 G的度数矩阵d[i][j] 当i≠j时d[i][j]=0 否则等于i点的度数 G的邻接矩阵a[i][j] a[i][j]=i.j间的边的个数(能有重边) Kirchhoff矩阵 c[i][j]=d[i][j]-a[i][j] Kirchhoff矩阵的n-1阶主子式的行列式的值的绝对值即为生成树的个数 n

uva10766生成树计数

此类题是给定一个无向图,求所有生成树的个数,生成树计数要用到Matrix-Tree定理(Kirchhoff矩阵-树定理) G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0:当i=j时,dij等于vi的度数 G的邻接矩阵A[G]也是一个n*n的矩阵, 并且满足:如果vi.vj之间有边直接相连,则aij=1,否则为0 我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:G的所有不同的生成树的个

HDU4305:Lightning(生成树计数+判断点是否在线段上)

Lightning Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2465    Accepted Submission(s): 912 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4305 Description: There are N robots standing on the