题解 | #继续畅通工程#

令weight为0即可
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Edge {
	int x;
	int y;
	int weight;
	bool finish;  //表示完成的状态
};

#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;
		Edge temp;
		for (int i = 0; i < n * (n - 1)/2; i++) {
			cin >> temp.x >> temp.y >> temp.weight >> temp.finish;
			if (temp.finish == true) 
				temp.weight = 0;

			vec.push_back(temp);
		}
		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;

	}
}