现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的 最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生 成树可能很多，所以你只需要输出方案数对31011的模就可以了。
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整 数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,0 00。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1
8
将权值相同的边看做一个边组。在MST中每个边组用的边数应该是固定的，并且起的是相同的作用（对连通性造成的变化相同） 因为具有相同权值的边不会超过10条，可以爆搜 并查集不能路径压缩，不然拆的时候会出错
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #define Mod 31011 using namespace std; struct Node{ int u,v,w; }Edges[2000]; int cnt=0,l[2000],r[2000],num[2000],father[105]; int read() { int f=1,x=0; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } return x*f; } bool cmp(Node x,Node y) { return x.w<y.w; } int find(int x) { if(x==father[x])return x; else return find(father[x]); } int sum; void dfs(int i,int j,int k) { if(j==r[i]+1) { if(k==num[i]) sum++; return; } int x=find(Edges[j].u),y=find(Edges[j].v); if(x!=y) { father[x]=y; dfs(i,j+1,k+1); father[x]=x; } dfs(i,j+1,k); } int n,m; int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int a,b,c; a=read();b=read();c=read(); Edges[i].u=a; Edges[i].v=b; Edges[i].w=c; } for(int i=1;i<=n;i++)father[i]=i; sort(Edges+1,Edges+1+m,cmp); int tot=0; for(int i=1;i<=m;i++) { if(i==1||Edges[i].w!=Edges[i-1].w) { l[++cnt]=i; r[cnt-1]=i-1; } int x=find(Edges[i].u),y=find(Edges[i].v); if(x!=y) { father[x]=y; tot++;num[cnt]++; } } r[cnt]=m; if(tot!=n-1)printf("0\n"); else { for(int i=1;i<=n;i++)father[i]=i; int ans=1; for(int i=1;i<=cnt;i++) { sum=0; dfs(i,l[i],0); ans*=sum; ans%=Mod; for(int j=l[i];j<=r[i];j++) { int x=find(Edges[j].u),y=find(Edges[j].v); if(x!=y)father[x]=y; } } printf("%d\n",ans); } return 0; }