题目链接:BZOJ1016-JSOI2008-最小生成树计数
题意:
给n个点,m条边,求这个图中有多少个不同的最小生成树,权值相同的边不会超过10条。
题解:
借助了两个定理:
- 不同的最小生成树中,每种权值的边出现的次数是相同的。
- 不同的生成树中,某一种权值的边连接完成后,形成的连通块是相同的。
这样就很简单了,只需要先做一次kruskal,计算出每种边权出现的次数,然后对于不同的边权依次进行暴搜,计算出相同边权集合中的不同解,然后乘法原理乘起来就可以了。
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=31011;
int n,m,tot,cnt,ans,sum;
int f[109];
struct Edge
{
int u,v,w;
} edge[1003];
bool cmp(Edge x,Edge y)
{
return x.w<y.w;
}
struct data
{
int l,r,w;
} a[1003];
int getf(int x)
{
if(x==f[x])
return x;
return getf(f[x]);
}
void dfs(int x,int now,int k)
{
if(now==a[x].r+1)
{
if(k==a[x].w)
sum++;
return;
}
int fx=getf(edge[now].u),fy=getf(edge[now].v);
if(fx!=fy)
{
f[fx]=fy;
dfs(x,now+1,k+1);
f[fx]=fx;
f[fy]=fy;
}
dfs(x,now+1,k);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
f[i]=i;
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<=m; i++)
{
if(edge[i].w!=edge[i-1].w)
{
a[cnt].r=i-1;
cnt++;
a[cnt].l=i;
}
int fx=getf(edge[i].u),fy=getf(edge[i].v);
if(fx!=fy)
{
f[fx]=fy;
a[cnt].w++;
tot++;
}
}
a[cnt].r=m;
if(tot!=n-1)
return puts("0"),0;
for(int i=1; i<=n; i++)
f[i]=i;
ans=1;
for(int i=1; i<=cnt; i++)
{
sum=0;
dfs(i,a[i].l,0);
ans=(ans*sum)%mod;
for(int j=a[i].l; j<=a[i].r; j++)
{
int fx=getf(edge[j].u),fy=getf(edge[j].v);
if(fx!=fy)
f[fx]=fy;
}
}
printf("%d\n",ans);
return 0;
}