1016: [JSOI2008]最小生成树计数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 6200 Solved: 2518
[Submit][Status][Discuss]

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,0
00。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过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

/*

* @Author: LyuC

* @Date:   2017-09-07 21:48:20

* @Last Modified by:   LyuC

* @Last Modified time: 2017-09-12 17:52:51

*/

/*

 题意：现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道

    这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则

    这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方

    案数对31011的模就可以了。

 思路：每个最小生成树的相同权值的边数是相同的，并且连通性是相同的，只需要枚举每个

    权值的相同连通性，并且是最小生成树中这个权值的个数的方案数，然后组合一下就行了

*/

#include <bits/stdc++.h>

#define MAXN 105

#define MAXM 1005

#define mod 31011

using namespace std;

struct Edge{

    int u,v,w;

    bool operator < (const Edge & other) const{

        return w<other.w;

    }

}edge[MAXM];

vector<Edge>v[MAXM];

int n,m;

int x,y,z;

int bin[MAXN];

int root[MAXN];

int vis[MAXM];//每种权值用到的数量

int sum;

int la;

int pos;

int res;

inline int findx(int x){

    int s=x;

    while(x!=bin[x])

        x=bin[x];

    bin[s]=x;

    return x;

}

inline int Count(int x){

    int s=;

    while(x){

        if(x%)

            s++;

        x/=;

    }

    return s;

}

inline void init(){

    for(int i=;i<=n;i++){

        bin[i]=i;

        root[i]=i;

    }

    memset(vis,,sizeof vis);

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

        v[i].clear();

    res=;

    pos=;

    sum=;

}

int main(){

    // freopen("in.txt","r",stdin);

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

    init();

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

        scanf("%d%d%d",&x,&y,&z);

        edge[i].u=x;

        edge[i].v=y;

        edge[i].w=z;

    }

    sort(edge,edge+m);

    //处理每种权值需要的边数

    la=-;

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

        if(edge[i].w!=la){

            la=edge[i].w;

            bool flag=false;

            for(int j=i;edge[j].w==la;j++){

                int fx=findx(edge[j].u);

                int fy=findx(edge[j].v);

                if(fx!=fy){

                    flag=true;

                    bin[fx]=fy;

                    vis[pos]++;

                    sum++;

                }

                v[pos].push_back(edge[j]);

            }

            pos++;

        }

    }

    if(sum!=n-){

        puts("");

        return ;

    }

    for(int i=;i<pos;i++){//枚举每个阶段用到权值的边

        if(vis[i]==) continue;

        int tol=(<<v[i].size());

        int cur=;//可以的方案

        for(int j=;j<tol;j++){

            if(Count(j)!=vis[i]) continue;

            bool flag=true;

            memcpy(bin,root,sizeof root);

            for(int k=;k<v[i].size();k++){

                if((j&(<<k))!=){//如果这条边存在

                    int fx=findx(v[i][k].u);

                    int fy=findx(v[i][k].v);

                    if(fx==fy){

                        flag=false;

                        break;

                    }else{

                        bin[fx]=fy;

                    }

                }

            }

            if(flag==true)

                cur++;

        }

        res=res*cur%mod;

        memcpy(bin,root,sizeof root);

        for(int j=;j<v[i].size();j++){

            int fx=findx(v[i][j].u);

            int fy=findx(v[i][j].v);

            if(fx!=fy){

                bin[fx]=fy;

            }

        }

        memcpy(root,bin,sizeof bin);

    }

    printf("%d\n",res%mod);

    return ;

}