题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=3371

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

给出城市的数量 n 以及 需要相联的城市及所需花销，再给出已经相联的城市。求将所有城市相联的最小花销。

对于已经相联的城市，我们也将他们视为没有相联，并且将花销置为0.这样就和普通的最小生成树一样了，从头开始寻找就可以了

【源代码】

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#define INF 0xfffffff
using namespace std;

int n,m,k;
const int maxn = 510;
struct node{
	int v,len;
	node(int v=0, int len = 0):v(v),len(len){}
};
vector <node> G[maxn];
int intree[maxn];
int minDist[maxn];
void init(){
	for(int i=0;i<maxn;i++){
		intree[i]=0;
		G[i].clear();
		minDist[i]=INF;
	}
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		init();
		scanf("%d%d%d",&n,&m,&k);
		int v1,v2,len;
		int start=1;
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&v1,&v2,&len);
			G[v1].push_back(node(v2,len));
			G[v2].push_back(node(v1,len));
			if(i==0)
				start = v1;
		}
		for(int i=0;i<k;i++){
			int n;
			scanf("%d",&n);
			int num[110];
			for(int j=0;j<n;j++){
				scanf("%d",&num[j]);
			}
			for(int j=0;j<n;j++){
				for(int k=j+1;k<n;k++){
					G[num[j]].push_back(node(num[k],0));
					G[num[k]].push_back(node(num[j],0));
				}
			}
		}
		int ans=prim(start);
		printf("%d\n",ans);
	}
	return 0;
}

hdu 3371 Connect the Cities（prim算法）

原文：http://blog.csdn.net/chaiwenjun000/article/details/47445887