题目 2401:
信息学奥赛一本通T1492-最小生成树计数
时间限制: 2s 内存限制: 192MB 提交: 18 解决: 8
题目描述
原题来自：JSOI 2008
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。
输入格式
第一行包含两个数，n 和 m，表示该无向图的节点数和边数，每个节点用 1∼n 的整数编号；
接下来的 m 行，每行包含两个整数：a,b,c，表示节点 a,b 之间的边的权值为 c。
输出格式
输出不同的最小生成树有多少个。你只需要输出数量对 31011 的模就可以了。
样例输入
复制
4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1样例输出
复制
8
思路：
首先，明确两条性质。
1.所有最小生成树的不同边权的数量一致。如一个图对应的所有最小生成树边权为1，2，3这样的边数固定不变，不会变成3条2，可以想象如果要换掉一条边，那么就必须那一条相等权的边换，大了就不是最小了，小了前一个就不是最小了。
2.相同边权的边所形成的联通块相同，可以想象kruskal建树过程，由小边到大边，小边够了之后联通块不变，等到有大边了，连通块才接着改变。
那么解题思路就变成了统计不同权边的使用方案数，再相乘即答案。
#include<bits/stdc++.h> using namespace std; const int N=110,M=1010,mod=31011; int n,m; int p[N]; struct edge{int a,b,w;bool operator<(edge&W){return w<W.w;} }e[M]; struct tree{int l,r,num,sum; }t[M]; int idx; int cnt; int k; int find(int x){if(x!=p[x]){return find(p[x]);}return x; } void dfs(int i,int q,int nu){if(nu==t[i].num){k++;return;}if(q>t[i].r){return;}int a=e[q].a;int b=e[q].b;int x=find(a);int y=find(b);if(x!=y){p[x]=y;dfs(i,q+1,nu+1);p[x]=x;}dfs(i,q+1,nu);return; } int main() {cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;e[i].a=a,e[i].b=b,e[i].w=c;}sort(e+1,e+1+m);for(int i=1;i<=n;i++){p[i]=i;}for(int i=1;i<=m;i++){int a=e[i].a;int b=e[i].b;int c=e[i].w;if(c!=e[i-1].w){idx++;t[idx].l=i;t[idx-1].r=i-1;}t[idx].sum++;int x=find(a);int y=find(b);if(x!=y){p[x]=y;t[idx].num++;cnt++;}}t[idx].r=m;if(cnt<n-1){cout<<0;return 0;}for(int i=1;i<=n;i++){p[i]=i;}int ans=1;for(int i=1;i<=idx;i++){//cout<<t[i].l<<endl;k=0;dfs(i,t[i].l,0);//cout<<k<<endl;if(k){ans=(long long )(ans*k)%mod;}for(int j=t[i].l;j<=t[i].r;j++){int a=e[j].a;int b=e[j].b;int x=find(a);int y=find(b);if(x!=y){p[x]=y;}}}cout<<ans; }