欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj1016

程序员文章站 2022-04-16 10:25:48
Description 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对31011的模就可以了。 现在给出了一个简 ......

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

8
 
最小生成树的 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;
}