题目链接:HDU4408-Minimum Spanning Tree
题意:
给n个点,m条边,求这个图中有多少个不同的最小生成树。
题解:
借助了两个定理:
- 不同的最小生成树中,每种权值的边出现的次数是相同的。
- 不同的生成树中,某一种权值的边连接完成后,形成的连通块是相同的。
因为权值相同的边的数量未知,所以只能用矩阵树定理去算。
对于权值相同的边,用矩阵树定理算出能够构成的最小生成树的数量,最后乘起来即可。
矩阵树定理:
- 记图的度数矩阵为A1(G),大小为n×n,i!=j时的元素为0,i=j时的元素为该点的度数。
- 记图的邻接矩阵为A2(G),大小为n×n,A2(i)(j)表示i与j两个点连通。
- 由以上两个矩阵可以构造出Kirchhoff矩阵:A(G)=A1(G)-A2(G)。
- 生成树的数量等于该Kirchhoff矩阵任何一个n-1阶柱子式的行列式的绝对值。
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=500;
const int MAXM=5000;
int n,m;
ll ans,sum,mod;
int fa[MAXN],ka[MAXN],used[MAXN];
ll mp[MAXN][MAXN],mat[MAXN][MAXN];
vector<int> gra[MAXN];
struct Edge
{
int u,v,w;
} edge[1009];
bool cmp(Edge x,Edge y)
{
return x.w<y.w;
}
int getf(int x,int father[])
{
if(x==father[x])
return x;
return father[x]=getf(father[x],father);
}
ll det(ll a[][MAXN],int n)
{
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a[i][j]%=mod;
ll ret=1;
for (int i=1; i<n; i++)
{
for (int j=i+1; j<n; j++)
while (a[j][i])
{
ll t=a[i][i]/a[j][i];
for (int k=i; k<n; k++)
a[i][k]=(a[i][k]-a[j][k]*t)%mod;
for (int k=i; k<n; k++)
swap(a[i][k],a[j][k]);
ret=-ret;
}
if (a[i][i]==0)
return 0;
ret=ret*a[i][i]%mod;
}
return (ret+mod)%mod;
}
void matrix_tree()
{
for(int i=1; i<=n; i++)
if(used[i])
{
gra[getf(i,ka)].push_back(i);
used[i]=0;
}
for(int k=1; k<=n; k++)
{
if(gra[k].size()>1)
{
memset(mat,0,sizeof(mat));
int len=gra[k].size();
for(int i=0; i<len; i++)
for(int j=i+1; j<len; j++)
{
int li=gra[k][i],lj=gra[k][j];
mat[j][i]-=mp[li][lj];
mat[i][j]=mat[j][i];
mat[i][i]+=mp[li][lj];
mat[j][j]+=mp[li][lj];
}
sum=det(mat,len);
sum%=mod;
ans=(ans%mod*sum%mod)%mod;
for(int i=0; i<len; i++)
fa[gra[k][i]]=k;
}
}
for(int i=1; i<=n; i++)
{
fa[i]=ka[i]=getf(i,fa);
gra[i].clear();
}
}
int main()
{
while(scanf("%d%d%lld",&n,&m,&mod)==3)
{
if(n==0&&m==0&&mod==0)
return 0;
memset(mp,0,sizeof(mp));
memset(used,0,sizeof(used));
for(int i=1; i<=m; i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
sort(edge+1,edge+1+m,cmp);
for(int i=1; i<=n; i++)
{
fa[i]=ka[i]=i;
gra[i].clear();
}
int temp=edge[1].w;
ans=1;
for(int i=1; i<=m; i++)
{
int fx=getf(edge[i].u,fa);
int fy=getf(edge[i].v,fa);
if(fx!=fy)
{
used[fx]=used[fy]=1;
ka[getf(fx,ka)]=getf(fy,ka);
mp[fx][fy]++;
mp[fy][fx]++;
}
if(i==m||edge[i+1].w!=temp)
{
matrix_tree();
temp=edge[i+1].w;
}
}
bool flag=1;
for(int i=2; i<=n; i++)
if(ka[i]!=ka[i-1])
{
flag=0;
puts("0");
break;
}
if(flag)
printf("%lld\n",ans%mod);
}
return 0;
}