首页 > > 程序设计 > C/C++ >

bzoj1016

2018-06-17 21:01:28来源：未知阅读 ()

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

最小生成树的 kruskal 并查集

按边的长度排序，因为不同的最小生成树方案，每种权值的边的数量是确定的，每种权值的边的作用是确定的（即若将相同长度的边放到一个集合里，无论这个集合中的边组成何种方案，最终形成的连通图是必然相同的） 

排序以后先做一遍最小生成树（Kruskal），得出每种权值的边使用的方案数


#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
int n,m,ct,fa[105],sum,ans=1,tot;
struct e{int u,v,wei;}edge[1004];
struct data{int l,r,wei;}a[1004];

inline int read(){
    char ch=getchar();int k=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){k=(k<<1)+(k<<3)+ch-'0';ch=getchar();}
    return k;
}

bool cmp(e a,e b){return a.wei<b.wei;}

int findfa(int x){return x==fa[x]?x:findfa(fa[x]);}// m^-w-^m 这里一定一定不能用路径压缩，否则在后面dfs中改变状态时会无法修改成功（被这里卡住了好久TwT） 

void dfs(int whic,int now,int muc){
    if(now==a[whic].r+1){if(muc==a[whic].wei)sum++;return;}
    int x=findfa(edge[now].u),y=findfa(edge[now].v);
    if(x!=y){fa[x]=y;dfs(whic,now+1,muc+1);fa[x]=x;fa[y]=y;}
    dfs(whic,now+1,muc);
}


int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){edge[i].u=read();edge[i].v=read();edge[i].wei=read();}
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;i++){//将相同权值的边归入一段“集合” 
        if(edge[i].wei!=edge[i-1].wei){a[ct].r=i-1;a[++ct].l=i;}
        int xx=findfa(edge[i].u),yy=findfa(edge[i].v);
        if(xx!=yy){fa[xx]=yy;tot++;a[ct].wei++;}
    }
    a[ct].r=m;
    if(tot!=n-1){printf("0");return 0;}//此时少于 n-1 条边必然无法形成最小生成树 
    for(int i=1;i<=n;i++) fa[i]=i;
       for(int i=1;i<=ct;i++)
    {
        sum=0;
        dfs(i,a[i].l,0);//求方案数 
        ans=(ans*sum)%31011;
        for(int j=a[i].l;j<=a[i].r;j++)//将本层形成的连通块连通（“连通”还是"联通"？这是个问题） 
        {
            int p=findfa(edge[j].u),q=findfa(edge[j].v);
            if(p!=q)fa[p]=q;
        }
    }
    printf("%d",ans);
    return 0;
}