学步园

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

此题与hdoj1233解法一样http://blog.csdn.net/xuguangsoft/article/details/7879572

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

int city[101];
struct Road {
	int c1, c2, cost;
};
Road road[5051];
int cmp(const Road a, const Road b)
{
	return a.cost < b.cost;
}
int Find(const int n)
{
	if (city[n] == -1)
		return n;
	return city[n] = Find(city[n]);
}
int Merge(const int a, const int b)
{
	int x = Find(a);
	int y = Find(b);
	if (x == y)
		return 0;
	if (x < y)
		city[y] = x;
	else
		city[x] = y;
	return 1;
}
int main()
{
	int n, m;
	int sum, count, i;
//	freopen("in.txt", "r", stdin);
	while (cin >> n >> m && n) {
		for (i = 0; i < n; i++) {
			cin >> road[i].c1 >> road[i].c2 >> road[i].cost;
		}
		sort(road, road+n, cmp);
		memset(city, -1, sizeof(city));
		sum = count = 0;
		for (i = 0; i < n; i++) {
			if (Merge(road[i].c1, road[i].c2)) {
				count ++;
				sum += road[i].cost;
			}
			if (count == m-1) break;
		}
		if (count != m-1) cout << "?" << endl;
		else cout << sum << endl;
	}
	return 0;
}