首页 > 代码库 > 生成树计数
生成树计数
生成树计数就是统计一张图中一共有多少种构造生成树的方案。
大概要用到组合数学等等的数学知识。
以下内容均来自NOI2007国家集训队论文 周冬 《生成树的计数及其应用》：
-------------------------
Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：
1、G的度数矩阵D[G]是一个n*n的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。
2、G的邻接矩阵A[G]也是一个n*n的矩阵， 并且满足：如果vi、vj之间有边直接相连，则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≤r≤n)，将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示。
在证明Matrix-Tree定理的过程中，我们使用了无向图G的关联矩阵B。B是一个n行m列的矩阵，行对应点而列对应边。B满足，如果存在一条边e={vi,vj}，那在e所对应的列中，vi和vj所对应的那两行，一个为1、另一个为-1，其他的均为0。至于谁是1谁是-1并不重要。
接下来，我们考察BBT。容易证明，(BBT)ij等于B的第i行与第j列的点积。所以，当i=j时，(BBT)ij等于与vi相连的边的个数，即vi的度数；而当i≠j时，如果有一条连接vi、vj的边，则(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。消元时需要求最小公倍数。还需要拓展欧几里得算法求逆元。
日后等有人能集我们队三者之大成之后，应该就可以挑战这道题了。
生成树计数