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