【kruscal】【最小生成树】【搜索】bzoj1016 [JSOI2008]最小生成树计数

浏览数：31 / 时间：2015年06月09日

不用Matrix-tree定理什么的，一边kruscal一边对权值相同的边暴搜即可。将所有方案乘起来。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m;
 5 struct Disjoint_Set
 6 {
 7     int fa[101],rank[101];
 8     void init(){for(int i=1;i<=n;i++) fa[i]=i;}
 9     int findroot(int x) 
10       {
11         if(fa[x]==x) return x;
12         int rt=findroot(fa[x]);
13         fa[x]=rt;
14         return rt;
15       }
16     void Union(int U,int V)
17       {
18         if(rank[U]<rank[V]) fa[U]=V;
19         else
20           {
21             fa[V]=U;
22             if(rank[U]==rank[V]) rank[U]++;
23           }
24       }
25 };
26 Disjoint_Set S,used;
27 struct Edge{int u,v,w;};
28 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}
29 Edge edges[1001];
30 int res,ans=1,tot,cnt,sta,end;
31 void dfs(int cur,int sum,Disjoint_Set now)
32 {
33     if(cur>end)
34       {
35           if(sum==cnt) res++;
36           return;
37       }
38     dfs(cur+1,sum,now);
39     int f1=now.findroot(edges[cur].u),f2=now.findroot(edges[cur].v);
40     if(f1!=f2) {now.Union(f1,f2); dfs(cur+1,sum+1,now);}
41 }
42 int main()
43 {
44     scanf("%d%d",&n,&m);
45     for(int i=1;i<=m;i++) scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
46     sort(edges+1,edges+m+1,cmp);
47     S.init();used.init();
48     for(int i=1;i<=m;i++)
49       {
50           if(edges[i].w!=edges[i-1].w) {used=S; cnt=0; sta=i;}
51           int f1=S.findroot(edges[i].u),f2=S.findroot(edges[i].v);
52           if(f1!=f2) {S.Union(f1,f2); tot++; cnt++;}
53           if(edges[i].w!=edges[i+1].w)
54             {
55                 res=0; end=i;
56                 dfs(sta,0,used);
57                 ans=((ans%31011)*(res%31011))%31011;
58             }
59           else if(tot==n-1)
60             {
61                 res=0;
62                 for(int j=i+1;j<=m;j++)
63                   if(edges[j].w!=edges[i].w)
64                     {
65                       end=j-1;
66                       goto OUT;
67                     }
68                 end=m;
69                 OUT:dfs(sta,0,used);
70                 ans=((ans%31011)*(res%31011))%31011;
71                 break;
72             }
73       }
74     printf("%d\n",tot==n-1 ? ans : 0);
75     return 0;
76 }