题解 | #还是畅通工程#

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
struct node {
	int a, b, w;
} no[N];
int n, m;
int p[N];

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

bool cmp(node x, node y) {
	return x.w < y.w;
}

int main() {
	while (cin >> n) {
		if (n == 0) return 0;
		m = n * (n - 1) / 2;
		for (int i = 1; i <= 100; i++) p[i] = i;
		for (int i = 1; i <= m; i++) cin >> no[i].a >> no[i].b >> no[i].w;
		sort(no + 1, no + 1 + m, cmp);
		int res = 0;
		for (int i = 1; i <= m; i++) {
			int a = find(no[i].a), b = find(no[i].b);
			if (a != b) {
				p[a] = b;
				res += no[i].w;
			}
		}
		cout << res << endl;
		memset(no, 0, sizeof no);
		res = 0;
	}
	return 0;
}