BZOJ 1016, 最小生成树计数

2019-11-10 21:36:29

字体：大中小

来源：转载

供稿：网友

PRoblem

传送门

Mean

给定一张简单无向加权图，求其最小生成树方案数。

Analysis

貌似有一个Matrix Tree定理……但是感觉目前不是很学得进东西，所以还是打了dfs。先跑一遍Kruskal，统计不同权值的边各出现几次。然后dfs判断某一种权值的边的方案数，累乘即可。需要注意的是并查集不可以路径压缩，那样会导致连通块合并后无法分开。

Code

#include<cstdio>#include<algorithm>using namespace std;const int N=105,M=1005,MOD=31011;int n,m,cnt,tot,ans=1,f[N];struct Edge{ int a,b,c; bool Operator < (const Edge &b) const {return c<b.c;}}e[M],t[M];int find(int x){return f[x]==x?x:find(f[x]);}int dfs(int x,int p,int cnt){ if(p==t[x].b+1) return cnt==t[x].c?1:0; int sum=0; int a=find(e[p].a),b=find(e[p].b); if(a!=b){ f[a]=b; sum+=dfs(x,p+1,cnt+1); f[a]=a,f[b]=b; } return sum+dfs(x,p+1,cnt);}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",&e[i].a,&e[i].b,&e[i].c);} sort(e+1,e+m+1); for(int i=1;i<=m;i++){ int a=find(e[i].a),b=find(e[i].b); if(e[i].c!=e[i-1].c){t[cnt].b=i-1,t[++cnt].a=i;} if(a!=b){ f[a]=b; t[cnt].c++,tot++; } } if(tot!=n-1){printf("0");return 0;} for(int i=1;i<=n;i++) f[i]=i; t[cnt].b=m; for(int i=1;i<=cnt;i++){ (ans*=dfs(i,t[i].a,0))%=MOD; for(int j=t[i].a;j<=t[i].b;j++){ int a=find(e[j].a),b=find(e[j].b); if(a!=b) f[a]=b; } } printf("%d",ans);}

上一篇：排序算法之归并排序

下一篇：Create Window