题面
有一张节点数为 (n), 边数为 (m) 的带权无向图 ((1le n le 100, 1 le m le 1000)),
求这张图有多少棵不同的最小生成树,
其中相同权值的边不超过 (10) 条.
思路
有一个定理/(结论?), 同一张图的不同最小生成树中, 每一种权值的边的数量相等, (并且从小到大把每种权值的边连完后, 图的连通性也一样).
所以权值不同的边之间没有干扰,
那我们只要分别计算每一种权值的边有多少种取的方案.
又因为相同权值的边不超过 (10) 条, 所以直接暴搜就行了.
然后还要特判一下图不连通的情况, 输出 (0).
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+7;
const int M=1e3+7;
const int mod=31011;
int n,m,fa[N],s=1,t=0,res=0,ans=1;
struct edge{
int x,y,w;
}e[M];
int find(int x){ return x==fa[x] ?x :find(fa[x]); }
void dfs(int k){
if(k>t){
bool flag=1;
for(int i=s;i<=t;i++) if(find(e[i].x)!=find(e[i].y)){ flag=0; break; }
res=(res+flag)%mod;
return;
}
int fx=find(e[k].x),fy=find(e[k].y);
if(fx!=fy){ fa[fx]=fy; dfs(k+1); fa[fx]=fx; }
dfs(k+1);
}
bool rule(edge a,edge b){ return a.w<b.w; }
int main(){
// freopen("x.in","r",stdin);
// freopen("x.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m,rule);
for(int i=1;i<=m;i=t+1){
s=i;
do{
t++;
e[t].x=find(e[t].x);
e[t].y=find(e[t].y);
}while(e[t+1].w==e[t].w&&t<=m);
res=0; dfs(s); ans=ans*res%mod;
for(int j=s;j<=t;j++)
if(e[j].x!=e[j].y) fa[find(e[j].x)]=find(e[j].y);
}
int rt=find(1);
for(int i=2;i<=n;i++) if(find(i)!=rt) ans=0;
printf("%d
",ans);
return 0;
}