题解 | #继续畅通工程#

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

using namespace std;

const int MAXN = 100;

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

Edge13501 edge13501[MAXN * MAXN];   //边集
int father13501[MAXN];              //父亲结点
int height13501[MAXN];              //结点高度

void Initial13501(int n) {     //初始化
	for (int i = 0; i <= n; i++) {
		father13501[i] = i;
		height13501[i] = 0;
	}
}

int Find13501(int x) {         //查找根结点
	if (x != father13501[x]) {
		father13501[x] = Find13501(father13501[x]);
	}
	return father13501[x];
}

void Union13501(int x, int y) { //合并集合
	x = Find13501(x);
	y = Find13501(y);
	if (x != y) {
		if (height13501[x] < height13501[y]) {
			father13501[x] = y;
		}
		else if (height13501[y] < height13501[x]) {
			father13501[y] = x;
		}
		else {
			father13501[y] = x;
			height13501[x]++;
		}
	}
	return;
}

int Kruskal13501(int n, int edgeNumber) {
	Initial13501(n);
	sort(edge13501, edge13501 + edgeNumber);    //按权值排序
	int sum = 0;
	for (int i = 0; i < edgeNumber; ++i) {
		Edge13501 current = edge13501[i];
		if (Find13501(current.from) != Find13501(current.to)) {
			Union13501(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) {
			int status;
			scanf("%d%d%d%d", &edge13501[i].from, &edge13501[i].to,
				&edge13501[i].length, &status);
			if (status == 1) {
				edge13501[i].length = 0;
			}
		}
		int answer = Kruskal13501(n, edgeNumber);
		printf("%d\n", answer);
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")