本文共 726 字，大约阅读时间需要 2 分钟。

题目大意： 求一张图有多少棵最小生成树。

题解

最小生成树有个性质，就是每种长度的边的数量是固定的。

所以先随便找一棵最小生成树，考虑长度为 $i$ 的边，先将长度不为 $i$ 的最小生成树中的边加入进去，然后就形成了若干个连通块，然后剩下的问题就是用长度为 $i$ 的边将这些连通块连成一棵树有多少种方案，显然用矩阵树定理就能求。

最后将每种长度的方案数乘起来就是答案了。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 110#define mod 31011int n,m,ans=1;struct edge{
   int x,y,z;}e[1010];int belong[maxn];bool v[1010];struct BCJ{
   	int fa[maxn];	void init(){
   for(int i=1;i<=n;i++)fa[i]=i;}	int findfa(int x){
   return x==fa[x]?x:fa[x]=findfa(fa[x]);}	bool linked(int x,int y){
   return findfa(x)==findfa(y);}	bool link(int x,int y)	{
   		x=findfa(x),y=findfa(y);		if(x==y)return false;		fa[y]=x;return true;	}}F;bool cmp(edge x,edge y){
   return x.z
     
    
   

转载地址：http://qpnib.baihongyu.com/