标签：最小生成树Kruskal
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,0
00。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过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
Sample Output
8
题意：给出一张图，求这张图不同的最小生成树个数
分析：Kruskal求最小生成树时间复杂度为O（n^2），这题可以跑两次最小生成树，第一次算出最终的结果，并且记录相同边权中起同样作用的边数量，第二次dfs回溯用乘法原理计算答案
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
LL f=1,x=0;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();}
return x*f;
}
const int maxn=1006,mod=31011;
struct edge{int x,y,v;}e[maxn];
struct node{int l,r,v;}a[maxn];
int n,m,cnt,tot,ans=1,sum,fa[106];
inline bool cmp(edge a,edge b){return a.v<b.v;}
inline int find(int x){return x==fa[x]?x:find(fa[x]);}
void dfs(int x,int now,int k)//寻找相同边权中符合最小生成树的边数量
{
if(now==a[x].r+1){
if(k==a[x].v)sum++;
return;
}
int r1=find(e[now].x),r2=find(e[now].y);
if(r1!=r2){
fa[r1]=r2;
dfs(x,now+1,k+1);
fa[r1]=r1,fa[r2]=r2;
}
dfs(x,now+1,k);
}
int main()
{
n=read(),m=read();
rep(i,1,n)fa[i]=i;
rep(i,1,m)e[i]=(edge){read(),read(),read()};
sort(e+1,e+1+m,cmp);//kruskal按边权大小排序
rep(i,1,m){
if(e[i].v!=e[i-1].v)a[++cnt].l=i,a[cnt-1].r=i-1;//统计不同边权的边个数（左边界和右边界）
int r1=find(e[i].x),r2=find(e[i].y);
if(r1!=r2){fa[r1]=r2;a[cnt].v++;tot++;}
}
a[cnt].r=m;
if(tot!=n-1){printf("0");return 0;}
rep(i,1,n)fa[i]=i;
rep(i,1,cnt){
sum=0;
dfs(i,a[i].l,0);
ans=(ans*sum)%mod;
rep(j,a[i].l,a[i].r){
int r1=find(e[j].x),r2=find(e[j].y);
if(r1!=r2)fa[r1]=r2;
}
}
cout<<ans<<endl;
return 0;
}
