图论之最小生成树计数（最小生成树的应用）

题目 2401: 

信息学奥赛一本通T1492-最小生成树计数

时间限制: 2s 内存限制: 192MB 提交: 18 解决: 8

题目描述

原题来自：JSOI 2008

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。

输入格式

第一行包含两个数，n 和 m，表示该无向图的节点数和边数，每个节点用 1∼n 的整数编号；

接下来的 m 行，每行包含两个整数：a,b,c，表示节点 a,b 之间的边的权值为 c。

输出格式

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

样例输入

复制

4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

样例输出

复制

8

思路：

首先，明确两条性质。

1.所有最小生成树的不同边权的数量一致。如一个图对应的所有最小生成树边权为1，2，3这样的边数固定不变，不会变成3条2，可以想象如果要换掉一条边，那么就必须那一条相等权的边换，大了就不是最小了，小了前一个就不是最小了。

2.相同边权的边所形成的联通块相同，可以想象kruskal建树过程，由小边到大边，小边够了之后联通块不变，等到有大边了，连通块才接着改变。

那么解题思路就变成了统计不同权边的使用方案数，再相乘即答案。

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010,mod=31011;
int n,m;
int p[N];
struct edge{
    int a,b,w;
    bool operator<(edge&W){
        return w<W.w;
    }
}e[M];
struct tree{
    int l,r,num,sum;
}t[M];
int idx;
int cnt;
int k;
int find(int x){
    if(x!=p[x]){
        return find(p[x]);
    }
    return x;
}
void dfs(int i,int q,int nu){
    if(nu==t[i].num){
        k++;
        return;
    }
    if(q>t[i].r){
        return;
    }
    int a=e[q].a;
    int b=e[q].b;
    int x=find(a);
    int y=find(b);
    if(x!=y){
        p[x]=y;
        dfs(i,q+1,nu+1);
        p[x]=x;
    }
    dfs(i,q+1,nu);
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[i].a=a,e[i].b=b,e[i].w=c;
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    for(int i=1;i<=m;i++){
        int a=e[i].a;
        int b=e[i].b;
        int c=e[i].w;
        if(c!=e[i-1].w){
            idx++;
            t[idx].l=i;
            t[idx-1].r=i-1;
        }
        t[idx].sum++;
        int x=find(a);
        int y=find(b);
        if(x!=y){
            p[x]=y;
            t[idx].num++;
            cnt++;
        }
    }
    t[idx].r=m;
    if(cnt<n-1){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    int ans=1;
    for(int i=1;i<=idx;i++){
        //cout<<t[i].l<<endl;
        k=0;
        dfs(i,t[i].l,0);
        //cout<<k<<endl;
        if(k){
           ans=(long long )(ans*k)%mod;
        }
        for(int j=t[i].l;j<=t[i].r;j++){
            int a=e[j].a;
            int b=e[j].b;
            int x=find(a);
            int y=find(b);
            if(x!=y){
                p[x]=y;
            }
        }
    }
    cout<<ans;
}