BZOJ1016:[JSOI2008]最小生成树计数(最小生成树,DFS)

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

Solution

有两条定理：

1.不同的最小生成树中,每种权值的边出现的个数是确定的。

2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的。

也就是说可以对于权值相同的那些边分别处理，爆搜出所有可能的连边情况，然后乘法原理计数即可。

Code

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define N (1009)

 #define MOD (31011)

 using namespace std;

 struct Edge

 {

     int x,y,v;

     bool operator < (const Edge &a) const{return v<a.v;}

 }E[N];

 struct Node{int l,r;}a[N];

 int n,m,k,fa[N],size[N],cnt,ans=,sum;

 int Find(int x){return x==fa[x]?x:Find(fa[x]);}

 void Dfs(int l,int r,int d,int v)

 {

     if (l>r)

     {

         if (d==size[v]) sum=(sum+)%MOD;

         return;

     }

     if (r-l++d<size[v]) return;

     int fx=Find(E[l].x), fy=Find(E[l].y);

     if (fx!=fy && d<size[v])

     {

         fa[fx]=fy;

         Dfs(l+,r,d+,v);

         fa[fx]=fx;

     }

     Dfs(l+,r,d,v);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=; i<=m; ++i)

         scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].v);

     sort(E+,E+m+);

     for (int i=; i<=n; ++i) fa[i]=i;

     for (int i=; i<=m; ++i)

     {

         if (E[i].v!=E[i-].v) a[++k].l=i, a[k-].r=i-;

         int fx=Find(E[i].x), fy=Find(E[i].y);

         if (fx!=fy) fa[fx]=fy,cnt++,size[k]++;

     }

     a[k].r=m;

     if (cnt!=n-){puts(""); return ;}

     for (int i=; i<=n; ++i) fa[i]=i;

     for (int i=; i<=k; ++i)

     {

         if (!size[i]) continue;

         sum=;

         Dfs(a[i].l,a[i].r,,i);

         ans=sum*ans%MOD;

         for(int j=a[i].l;j<=a[i].r;j++)

         {

             int fx=Find(E[j].x), fy=Find(E[j].y);

             if(fx!=fy) fa[fx]=fy;

         }

     }

     printf("%d\n",ans);

 }

秒客网