题目大意:和基本的最小生成树想比,其在最开始的时候有多个起点,从任一起点开始生成都可以。
一直到最后才发现做法,就是把起始点都提前加入生成树里面。
#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()); } }
uva 6437 - Power Plant【最小生成树】,布布扣,bubuko.com
原文:http://blog.csdn.net/u010468553/article/details/38511447