首页 > 代码库 > uva 6437 - Power Plant【最小生成树】
uva 6437 - Power Plant【最小生成树】
题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4448
题目大意:和基本的最小生成树想比,其在最开始的时候有多个起点,从任一起点开始生成都可以。
一直到最后才发现做法,就是把起始点都提前加入生成树里面。
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; #define maxn 205 int T,N,M,K; int f[maxn]; struct node { int u,v,w; bool operator<(const node &a)const { return w<a.w; } }a[maxn]; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } int kruscal() { sort(a,a+M); int sum=0; for(int j=0;j<M;j++) { int x=find(a[j].u); int y=find(a[j].v); if(x!=y) sum+=a[j].w,f[y]=x; } return sum; } int main () { int fa,tem; scanf("%d",&T); for(int ii=1;ii<=T;ii++) { scanf("%d%d%d",&N,&M,&K); for(int i=0;i<=N;i++) f[i]=i; scanf("%d",&fa); for(int j=1;j<K;j++) { scanf("%d",&tem); f[tem]=fa; } for(int j=0;j<M;j++) scanf("%d%d%d",&a[j].u,&a[j].v,&a[j].w); printf("Case #%d: %d\n",ii,kruscal()); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。