3
17
2016
0

【生成树计数】合集~

给定一个无向图G,求它生成树的个数t(G)。

O(3n*n2) :dp

O(n3):Matrix-Tree定理(Kirchhoff矩阵-树定理):

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

计算行列式的时间复杂度为O(n3),因此,生成树的计数也可以在O(n3)的时间内完成。

 

证明的关键:

(Binet-Cauchy公式) 设AB各为p*qq*p矩阵,则有

 

特别的,detAAT=(detA)2

Binet-Cauchy公式展开式中的每一项对应着边集一个大小为n-1的子集。

其中,值为1的项对应一颗生成树,而没有对应生成树的项值为0。

这样,将问题转化为求展开式中所有项之和。

 

模板题 :【SPOJ104】Highways

计算基尔霍夫矩阵(拉普拉斯矩阵)L:

L=D-A

D:度矩阵当i≠j时,dij=0;当i=j时,dij等于vi的度数

A:邻接矩阵如果vi、vj之间有边直接相连,则aij=1,否则为0


double D[N][N],A[N][N],L[N][N],deg[N];
F(i,1,m){
	int x,y;
	x=read();y=read();
	A[x][y]=A[y][x]=1;
	deg[x]++;deg[y]++;
}
F(i,1,n) F(j,1,n) D[i][i]=deg[i];
F(i,1,n) F(j,1,n) L[i][j]=D[i][j]-A[i][j];
ans=Gauss(L);

高斯消元求行列式:

注意:1\主子式2\绝对值

默认去掉第n行第n列, 消成上三角矩阵

inline double Gauss(double a[][N])
{
	double ans=1;
	int t=1;
	for(int i=1;i<n;i++){//【枚举当前行 
		int r=i;
		for(int j=i+1;j<n;j++)//【枚举下面的行 
			if(abs(a[j][i])>abs(a[r][i])) r=j;//r记录第i列最大值 
		if(r!=i){ 
			t=-t;//行列式性质 
			for(int j=1;j<=n;j++) swap(a[r][j],a[i][j]);//两行所有数调换 
		}
	//与第i+1~n-1行所有数进行消元(均消为0) 
		for(int k=i+1;k<n;k++){
			double p=1.0*a[k][i]/a[i][i];////a[k][i]-a[k][i]/(a[i][i]*a[i][i])=0
			for(int j=i;j<n;j++) a[k][j]-=p*a[i][j];//第二重循环枚举该行数字 
		}
	}
	//与高斯消元不同:不合并,而是对角线相乘 
	for(int i=1;i<n;i++) ans*=a[i][i];
	return ans*t;
}		

[当前求行列式的模板可能还不完善]

 


 

给出一个简单无向加权图,求图中不同的最小生成树个数。(如果两棵最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。

模板题:[JSOI2008]最小生成树计数

输出方案数对31011的模

最小生成树的两个性质:

1、边权相等的边的个数一定。

2、做完边权为w的所有边时,图的连通性相同。

挖坑:http://www.cnblogs.com/Tunix/p/4415971.html

 


用三种颜色给每条边染色,给出特定的边可染的颜色,

求不同染色方案的生成树数量

 

这个有点难...证明要用拉格朗日插值&%#¥...

Category: 生成树 | Tags: 生成树 线性代数 数论 动态规划 | Read Count: 492

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com