Connect the Cities

1
6 4 3
1 4 2
2 6 1
2 3 5
3 4 33
2 1 2
2 1 3
3 4 5 6

1

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <climits>

using namespace std;

const int MAX = 25003;

typedef struct Road{
	int x;
	int y;
	int c;
}Road;

Road road[MAX];
int cr;

int pre[501];

void init(int n){
	int i;
	for(i=1;i<=n;++i){
		pre[i] = i;
	}
	cr = n-1;
}

int root(int x){
	if(x!=pre[x]){
		pre[x] = root(pre[x]);
	}
	return pre[x];
}

int merge(int x,int y){
	if(x==-1)return 0;
	int ret = 0;
	int fx = root(x);
	int fy = root(y);
	if(fx!=fy){
		--cr;
		pre[fx] = fy;
		ret = 1;
	}
	return ret;
}

int cmp(const void *a,const void *b){
	return ((Road *)a)->c - ((Road *)b)->c;
}

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t,n,m,k,cid,tc,pre;
	int sum,i,j;
	scanf("%d",&t);
	while(t--){
		scanf("%d %d %d",&n,&m,&k);
		init(n);
		for(i=0;i<m;++i){
			scanf("%d %d %d",&road[i].x,&road[i].y,&road[i].c);
		}
		sum = 0;
		for(i=0;i<k;++i){
			scanf("%d",&tc);
			pre = -1;
			for(j=0;j<tc;++j){
				scanf("%d",&cid);
				merge(pre,cid);
				pre = cid;
			}
		}
		qsort(road,m,sizeof(Road),cmp);
		for(i=0;i<m;++i){
			if(merge(road[i].x,road[i].y)==1){
				sum += road[i].c;
			}
		}
		if(cr!=0){
			printf("-1\n");
		}else{
			printf("%d\n",sum);
		}
	}
    return 0;
}

HDU 3371 Connect the Cities (最小生成树 并查集+克鲁斯卡尔),布布扣,bubuko.com

HDU 3371 Connect the Cities (最小生成树 并查集+克鲁斯卡尔)

原文：http://blog.csdn.net/iaccepted/article/details/24121209