题解 | #还是畅通工程#

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

struct Edge {
	int x;
	int y;
	int weight;
};

#define N 1000 //元素的上限个数
int father[N];
int height[N];

bool compare(Edge lhs, Edge rhs) {
	return lhs.weight < rhs.weight;
}


void Init(int n) {
	for (int i = 1; i <= n; i++) {
		father[i] = i;
		height[i] = 1;
	}
}

int Find(int x) {
	if (x != father[x]) {
		father[x] = Find(father[x]);
	}
	return father[x];

}

void Union(int x, int y, int weight,int & total) {
	x = Find(x); y = Find(y);
	if (x != y) {  //判断x与y是否属于同一集合
		total += weight;  
	}
	if (height[x] < height[y])
		father[x] = y;
	else if (height[x] > height[y])
		father[y] = x;
	else {
		father[y] = x;
		++height[x];
	}
}

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) break;
		Init(n);
		vector<Edge> vec;
		for (int i = 0; i < n * (n - 1) / 2; i++) {
			Edge edge;
			cin >> edge.x >> edge.y >> edge.weight;
			vec.push_back(edge);
		}
		sort(vec.begin(), vec.end(), compare);  //给边权进行排序
		int total = 0; //表示权值之和
		for (int i = 0; i < n * (n - 1) / 2; i++) {
			Union(vec[i].x, vec[i].y, vec[i].weight ,total);  //要判断是否已经在同一集合中

		}
		cout << total << endl;
	}




}