题解 | #继续畅通工程#

//并查集+krustal，如果已经修建道路则直接将两个点合并
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int father[101];
struct Edge;
vector<Edge>Edge_list;
void initConfig()
{
	for (int i = 0; i < 101; i++)
	{
		father[i] = i;
	}
	Edge_list.clear();
}
int findFather(int x)
{
	if (x == father[x])
	{
		return x;
	}
	else
	{
		father[x] = findFather(father[x]);
		return father[x];
	}
}
void unionFather(int x, int y)
{
	int x_father = findFather(x);
	int y_father = findFather(y);
	father[y_father] = father[x_father];
}

struct  Edge
{
	int U, V, WEIGHT;
	Edge(int a, int b, int c)
	{
		U = a; V = b; WEIGHT = c;
	}
};

bool cmp(Edge a, Edge b)
{
	return a.WEIGHT < b.WEIGHT;
}

int krustal(int N_nodes, int union_count)
{
	sort(Edge_list.begin(), Edge_list.end(), cmp);
	int sum = 0;
	int count = 0;
	for (int i = 0; i < Edge_list.size(); i++)
	{
		Edge e = Edge_list[i];
		if (findFather(e.U) != findFather(e.V))
		{
			sum = sum + e.WEIGHT;
			unionFather(e.U, e.V);
			count++;
		}
		if (count == N_nodes - 1 - union_count)
		{
			break;
		}
	}
	return sum;

}

int main()
{
	int N;
	while (scanf("%d", &N) != EOF)
	{
		if (N == 0)
		{
			break;
		}
		initConfig();
		int union_count = 0;
		for (int i = 0; i < N * (N - 1) / 2; i++)
		{
			int U, V, weight, conection;
			scanf("%d %d %d %d", &U, &V, &weight, &conection);
			if (conection == 0)
			{
				Edge_list.push_back(Edge(U, V, weight));
				//Edge_list.push_back(Edge(V, U, weight));
			}
			else
			{
				unionFather(U, V);
				union_count++;
			}
		}
		int sum = krustal(N, union_count);
		cout << sum << endl;

	}
}