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
Sample Output
8
网上的题解基本上没有证明（或许有，但是我没看见，然后懒得找了）
两个最小生成树的权值相同的边作用相同（连通情况）
我们可以用反证法
假设有两个最小生成树的权值相同的边作用不同，那么把最小的作用不同的权值找出来
然后我们把他们的连通情况合并（去环），需要的边肯定会变多，而且一定可以做到，相当于我们用多出来的边代替了权值比它大的边，那这与前面说的这是最小生成树矛盾
例：假设权值为1的边在一棵最小生成树里造成连通情况是（1,2）（3,4），在另一棵最小生成树里造成的连通情况是（1,4）（2,3）
那我们可以合并它们用权值为1的边做到（1,2,3,4）,来替换一条权值大于1的边，得到一颗权值更小的树
证毕.
所以我们记录每种权值的边所造成的连通情况记录下来，每个权值做一遍，乘起来就是答案（注意判断无解的情况）
1 const 2 maxn=105; 3 maxm=1010; 4 h=31011; 5 var 6 ans,n,m,l:longint; 7 u,v,w:array[0..maxm]of longint; 8 a:array[0..10,0..1024]of longint; 9 10 procedure swap(var x,y:longint); 11 var 12 t:longint; 13 begin 14 t:=x;x:=y;y:=t; 15 end; 16 17 procedure sort(l,r:longint); 18 var 19 i,j,y:longint; 20 begin 21 i:=l; 22 j:=r; 23 y:=w[(l+r)>>1]; 24 repeat 25 while w[i]<y do 26 inc(i); 27 while w[j]>y do 28 dec(j); 29 if i<=j then 30 begin 31 swap(u[i],u[j]); 32 swap(v[i],v[j]); 33 swap(w[i],w[j]); 34 inc(i); 35 dec(j); 36 end; 37 until i>j; 38 if i<r then sort(i,r); 39 if j>l then sort(l,j); 40 end; 41 42 function bit(x:longint):longint; 43 begin 44 if x=0 then exit(0); 45 exit(bit(x-(x and -x))+1); 46 end; 47 48 procedure init; 49 var 50 i,k:longint; 51 begin 52 read(n,m); 53 for i:=1 to m do 54 read(u[i],v[i],w[i]); 55 sort(1,m); 56 for i:=0 to 1023 do 57 begin 58 k:=bit(i); 59 inc(a[k,0]); 60 a[k,a[k,0]]:=i; 61 end; 62 end; 63 64 var 65 f,f2,vis:array[0..maxn]of longint; 66 xu:array[0..maxm]of longint; 67 time:longint; 68 69 function find(x:longint):longint; 70 begin 71 if vis[x]<>time then 72 begin 73 f[x]:=f2[x]; 74 vis[x]:=time; 75 end; 76 if f[x]=x then exit(x); 77 f[x]:=find(f[x]); 78 exit(f[x]); 79 end; 80 81 function find2(x:longint):longint; 82 begin 83 if f2[x]=x then exit(x); 84 f2[x]:=find2(f2[x]); 85 exit(f2[x]); 86 end; 87 88 function flag(x:longint):boolean; 89 var 90 i:longint; 91 begin 92 i:=0; 93 while x>0 do 94 begin 95 inc(i); 96 if x and 1=1 then 97 begin 98 if find(u[l+i])=find(v[l+i]) then exit(false); 99 if (f[u[l+i]]<>f[v[l+i]])and(find2(u[l+i])=find2(v[l+i])) then exit(false); 100 f[f[u[l+i]]]:=f[v[l+i]]; 101 end; 102 x:=x>>1; 103 end; 104 exit(true); 105 end; 106 107 procedure work; 108 var 109 i,j,s,last:longint; 110 begin 111 ans:=1; 112 for i:=1 to n do 113 f2[i]:=i; 114 for i:=1 to m do 115 begin 116 if w[i]=w[i-1] then xu[i]:=xu[i-1]; 117 if find2(u[i])<>find2(v[i]) then 118 begin 119 inc(xu[i]); 120 f2[f2[u[i]]]:=f2[v[i]]; 121 end; 122 end; 123 for i:=1 to n-1 do 124 if find2(i)<>find2(i+1) then ans:=0; 125 for i:=1 to n do 126 f2[i]:=i; 127 l:=0; 128 last:=0; 129 for i:=1 to m do 130 if w[i]<>w[i+1] then 131 begin 132 s:=0; 133 while last<l do 134 begin 135 inc(last); 136 f2[find2(u[last])]:=find2(v[last]); 137 end; 138 for j:=1 to a[xu[i],0] do 139 begin 140 if a[xu[i],j]>=1<<(i-l) then break; 141 inc(time); 142 if flag(a[xu[i],j]) then inc(s); 143 end; 144 l:=i; 145 ans:=ans*s mod h; 146 end; 147 write(ans); 148 end; 149 150 begin 151 init; 152 work; 153 end.