最小生成树计数
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树 可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第 一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10 条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
8
思路:为什么会有多棵最小生成树?由于边权值相等的构成了环，所以可以从中选出若干条权值相等的边(保证连通性即可)而得到了多棵MST;
启发:直接按照边的权值排序，贪心地从小到大取边，在边权相等的所有边中进行深搜，因为在MST中，每种边权的边的个数和作用是确定的，再利用乘法原理即可得到全部边得到的MST的个数了；
编程细节:重新创建一个结构体，用来存储每种边权的边的id的左右边界以及这种边权的个数，在深搜中使用朴素的并查集来判断是否出现环即可；并查集不能进行压缩，否则MST的数量会减少了；
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define MK make_pair template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } const int mod = 31011; const int N = 111; const int M = 1011; struct edge{int u,v,w;}e[M]; bool cmp(const edge& a,const edge& b){return a.w < b.w;} struct data{int l,r,s;}d[M]; int f[N],sum; int Find(int a) { return a == f[a] ?f[a]:Find(f[a]);// ** } void dfs(int x,int now,int p) { if(now == d[x].r+1){ if(p == d[x].s) sum++; return ; } int fu = Find(e[now].u), fv = Find(e[now].v); if(fu != fv){ f[fu] = fv; dfs(x,now+1,p+1); f[fu] = fu; } dfs(x,now+1,p); } int main() { int n,m; read2(n,m); rep1(i,1,m) read3(e[i].u,e[i].v,e[i].w); sort(e+1, e+1+m,cmp); int cnt = 0,tot = 0; rep1(i,1,n) f[i] = i; rep1(i,1,m){ if(e[i].w != e[i - 1].w){ d[cnt].r = i - 1; d[++cnt].l = i; } int fu = Find(e[i].u), fv = Find(e[i].v); if(fu != fv){ f[fu] = fv; tot++; d[cnt].s++;// 边权相同的边的个数 } } d[cnt].r = m; if(tot != n - 1)return puts("0"),0;//判断图是否连通 rep1(i,1,n) f[i] = i; int ans = 1; rep1(i,1,cnt){ sum = 0; dfs(i,d[i].l,0); ans = ans*sum%mod; rep1(j,d[i].l,d[i].r){ int u = e[j].u, v = e[j].v; int fu = Find(u), fv = Find(v); if(fu != fv) f[fu] = fv; } } cout<<ans; return 0; }