题解 | #还是畅通工程#

//土尔逊Torson 编写于2023/06/21
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100;

struct Edge13001 {
	int from;      //边的起点
	int to;        //边的终点
	int length;    //边的长度
	bool operator<(const Edge13001& e) const {
		return length < e.length;
	}
};

Edge13001 edge13001[MAXN*MAXN]; //边集
int father13001[MAXN];     //父亲结点
int height13001[MAXN];     //结点高度

void Initial13001(int n) { //初始化
	for (int i = 0; i <= n; i++) {
		father13001[i] = i;
		height13001[i] = 0;
	}
}

int Find13001(int x) {
	if (x != father13001[x]) {
		father13001[x] = Find13001(father13001[x]);
	}
	return father13001[x];
}

void Union13001(int x, int y) {
	x = Find13001(x);
	y = Find13001(y);
	if (x != y) {
		if (height13001[x] < height13001[y]) {
			father13001[x] = y;
		}
		else if (height13001[y] < height13001[x]) {
			father13001[y] = x;
		}
		else {
			father13001[y] = x;
			height13001[x]++;
		}
	}
	return;
}

int Kruskal(int n, int edgeNumber) {
	Initial13001(n);
	sort(edge13001, edge13001 + edgeNumber); //按权值排序
	int sum = 0;
	for (int i = 0; i < edgeNumber; ++i) {
		Edge13001 current = edge13001[i];
		if (Find13001(current.from) != Find13001(current.to)) {
			Union13001(current.from, current.to);
			sum += current.length;
		}
	}
	return sum;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		int edgeNumber = n*(n - 1) / 2;
		for (int i = 0; i < edgeNumber; ++i) {
			scanf("%d%d%d", &edge13001[i].from, &edge13001[i].to, &edge13001[i].length);
		}
		int answer = Kruskal(n, edgeNumber);
		printf("%d\n", answer);
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")