学步园

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

最小生成树问题：prim算法

#include <iostream>
#include <algorithm>
using namespace std;

struct Road {
	int c1, c2, cost;
};
Road road[5051];
int city[101];//统一将大序号指向小序号，形成树的根可由最小序号充当

int cmp(const Road a, const Road b) {
	return a.cost < b.cost;
}
int Findnext(const int n) {//查找与之相连接的城市
	if (city[n] == -1) return n;
	return city[n] = Findnext(city[n]);//压缩路径
}
int Merge(const int a, const int b) {//合并
	int x = Findnext(a);
	int y = Findnext(b);
	if (x == y) return 0;
	if (x < y)
		city[y] = x;
	else
		city[x] = y;
	return 1;
}
int main()
{
	int n, m;
	int i, sum, count;
//	freopen("in.txt","r",stdin);
	while (cin >> n && n) {
		m = n*(n-1)/2;
		for (i = 0; i < m; i++) {
			cin >> road[i].c1 >> road[i].c2 >> road[i].cost;
		}
		sort(road, road+m, cmp);
		memset(city, -1, sizeof(city));
		sum = 0;
		count = 0;
		for (i = 0; i < m; i++) {
			if (Merge(road[i].c1, road[i].c2)) {
				count ++;
				sum += road[i].cost;
			}
			if (count == n-1)
				break;
		}
		cout << sum << endl;
	}
	return 0;
}