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
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
8
正解：克鲁斯卡尔最小生成树+搜索
解题报告：
今天考场上考了一道这个题目，我居然没看出来就是一道求最小生成树个数的裸题。。。
今天考场上考了一道这个题目，我居然没看出来就是一道求最小生成树个数的裸题。。。
说起来还是挺水的，就是有许多性质还掌握的不够熟练。不同的最小生成树方案，每种权值的边的数量是确定的，每种权值的边的作用是确定的。所以每种权值看作一个集合，这个集合若想对最终结果产生贡献，即是最小生成树，需要选取的边数是固定的。
排序以后先做一遍最小生成树，得出每种权值的边使用的数量x
然后对于每一种权值的边搜索，得出每一种权值的边选择方案。就是枚举某条边选不选，暴力搜索是否可行。（因为题目说同种权值不超过10，所以指数级大暴力不虚）
最后乘法原理，每一步的方案数相乘。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const int MOD = ;
int n,m;
int first[MAXN],next[MAXM],to[MAXM];
int cnt;
int father[MAXN];
int ans,lin; struct build{
int l,r,cnt;
}a[MAXM]; struct edge{
int x,y,z;
}e[MAXM]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline bool cmp(edge q,edge qq){ return q.z<qq.z; } inline int find(int x){
//不能路径压缩！！！
if(father[x]!=x) return find(father[x]); //father[x]=find(father[x]);
return father[x];
} inline void dfs(int x,int now,int gong){
if(now==a[x].r+) {
if(gong==a[x].cnt) lin++;//必须选指定的条数
return ;
}
int r1=find(e[now].x),r2=find(e[now].y);
if(r1!=r2) {//枚举选还是不选
father[r1]=r2;
dfs(x,now+,gong+);
father[r1]=r1; father[r2]=r2;
}
dfs(x,now+,gong);//不选
} inline void solve(){
n=getint(); m=getint();
int x,y,z;
for(int i=;i<=m;i++) {
x=getint(); y=getint(); z=getint();
e[i].x=x; e[i].y=y; e[i].z=z;
} sort(e+,e+m+,cmp); for(int i=;i<=n;i++) father[i]=i; int gg=;
for(int i=;i<=m;i++) {
if(e[i].z!=e[i-].z) { cnt++; a[cnt].l=i; a[cnt-].r=i-; }
int r1=find(e[i].x),r2=find(e[i].y);
if(r1!=r2) {
father[r2]=r1;
a[cnt].cnt++;
gg++;
//if(gg==n-1) break;
}
}
a[cnt].r=m; if(gg!=n-) { printf(""); return ; }
for(int i=;i<=n;i++) father[i]=i; ans=;
for(int i=;i<=cnt;i++) {
lin=;
dfs(i,a[i].l,);
ans*=lin; if(ans>=MOD) ans%=MOD; for(int j=a[i].l;j<=a[i].r;j++) {
int r1=find(e[j].x),r2=find(e[j].y);
if(r1!=r2) father[r2]=r1;
}
} printf("%d",ans);
} int main()
{
solve();
return ;
}