题解 | #继续畅通工程#

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

const int N = 110;
int p[N], h[N];

struct Edge {
	int x, y, v, st;
	bool operator < (const Edge &w) const {
		return v < w.v;
	}
} edge[5000];

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

void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (h[x] < h[y]) p[x]  = y;
	else if (h[y] < h[x]) p[y] = x;
	else p[y] = x, h[x]++;
}

int kruskal(int n, int num) {
	for (int i = 0; i <= n; i++) p[i] = i, h[i] = 0;
	int cost = 0;
	for (int i = 0; i < num; i++) {
		int x = edge[i].x;
		int y = edge[i].y;
		if (Find(x) != Find(y)) {
			Union(x, y);
			cost += edge[i].v;
		}
	}
	return cost;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) break;
		int num = n * (n - 1) / 2;
		for (int i = 0; i < num; i++) {
			scanf("%d%d%d%d", &edge[i].x, &edge[i].y, &edge[i].v, &edge[i].st);
			if (edge[i].st == 1) edge[i].v = 0;
		}
		sort(edge, edge + num);
		int cost = kruskal(n, num);
		printf("%d\n", cost);
	}
	return 0;
}