BZOJ-1016: [JSOI2008]最小生成树计数 (kruscal+搜索)

　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的
最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生
成树可能很多，所以你只需要输出方案数对31011的模就可以了。

　　第一行包含两个数，n和m，其中1数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中100。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。

　　输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX1=105;
 5 const int MAX2=1005;
 6 int n,m,fa[MAX1],tot,sum,ans;
 7 struct Edge{
 8     int u,v,w;
 9     bool operator const Edge &tt) const {
10         return wtt.w;
11     }
12 }edge[MAX2];
13 struct Node{int low,high,num;Node(){num=0;}}a[MAX2];int cnt;//存放权值相同的边的最左边的一条，最右边的一条以及产生作用的条数 
14 int getfather(int x){return fa[x]==x?x:getfather(fa[x]);}
15 inline int read(){
16     int an=0,x=1;char c=getchar();
17     while (c‘0‘ || c>‘9‘) {if (c==‘-‘) x=-1;c=getchar();}
18     while (c>=‘0‘ && c‘9‘) {an=an*10+c-‘0‘;c=getchar();}
19     return an*x;
20 }
21 void dfs(int x,int now,int k){//x表示现在正在处理第x种边,now表示正在处理第i条边,k表示当前合并集合的次数 
22     if (now==a[x].high+1){
23         if (k==a[x].num) sum++;
24         return;
25     }
26     int tx=getfather(edge[now].u);
27     int ty=getfather(edge[now].v);
28     if (tx!=ty){
29         fa[tx]=ty;
30         dfs(x,now+1,k+1);
31         fa[tx]=tx,fa[ty]=ty;//回溯
32     }
33     dfs(x,now+1,k);
34 }
35 int main(){
36     freopen ("count.in","r",stdin);
37     freopen ("count.out","w",stdout);
38     int i,j;
39     n=read(),m=read();
40     for (i=1;iread();
41     sort(edge+1,edge+m+1);
42     for (i=1;ii;
43     for (i=1;i){
44         if (edge[i].w!=edge[i-1].w) a[++cnt].low=i,a[cnt-1].high=i-1;
45         int tx=getfather(edge[i].u);
46         int ty=getfather(edge[i].v);
47         if (tx!=ty){
48             fa[tx]=ty;
49             a[cnt].num++;
50             tot++;
51         }
52     }
53     a[cnt].high=m;
54     if (tot!=n-1){puts("0");return 0;}
55     for (i=1;ii;
56     for (ans=i=1;i){
57         sum=0;
58         dfs(i,a[i].low,0);
59         ans=(ans*sum)%31011;
60         for (j=a[i].low;j){
61             int tx=getfather(edge[j].u);
62             int ty=getfather(edge[j].v);
63             if (tx!=ty)
64                 fa[tx]=ty;
65         }
66     }
67     printf("%d",ans);
68     return 0;
69 }