题解 | 继续畅通工程

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

const int N = 110;
int p[N];//保存所有结点的状态
struct edge {
	int u, v, w, state;
	edge(int u, int v, int w, int state) {
		this->u = u, this->v = v, this->w = w, this->state = state;
	}
	edge() {

	}
	bool operator < (const edge&m) const{
		return this->w < m.w;
	}
};

int find(int x) {
	if (p[x] != x)p[x] = find(p[x]);
	return p[x];
}
int main() {
	int n;
	while (cin >> n) {
		if(n==0)break;
		vector<edge> E;
		int count = 0;//已经选的边的数量，有些边已经存在，考虑在此情况下怎么才能成本最低
		//初始化并查集
		for (int i = 1; i <= n; i++) {
			p[i] = i;
		}
		for (int i = 1; i <= n * (n - 1) / 2; i++) {
			int u, v, w, state;
			cin >> u >> v >> w >> state;
			if(!state)
				E.push_back(edge(u, v, w, state));//未修建的话要放入动态数组中，接下来选
			else {
				//已经存在的路要加入并查集
				int root1 = find(u);
				int root2 = find(v);
				if (root1 != root2)p[root1] = root2;
				count++;
			}
		}
		
		sort(E.begin(), E.end());
		int cost = 0;
		//因为我用的是动态数组，插入是从0位置开始插入的
		for (int i = 0; i < E.size();i++) {
			int u = E[i].u, v = E[i].v, w = E[i].w;
			if (find(u) != find(v)) {
				//当两个点不在一个集合时，要选这条边
				int root1 = find(u);
				int root2 = find(v);
				p[root1] = root2;
				cost += w;
				count++;
			}
			if (count == n - 1)break;//已经找到生成树的话可以提前退出
		}
		cout << cost << endl;
	}
	
	return 0;
}
//啊啊啊Kruskal算法好好用