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
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; }
上一篇: 音视频和表单的详情