题解 | #还是畅通工程#

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int father[200];

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;
	int 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 main()
{
	int N;
	while (scanf("%d", &N)!=EOF)
	{
		if (N == 0)
		{
			break;
		}
		for (int i = 0; i < 200; i++)
		{
			father[i] = i;
		}
		vector<Edge>edge_list;
		for(int i=0;i< N*(N - 1) / 2;i++)
		{
			int U, V, weight;
			scanf("%d %d %d", &U, &V, &weight);
			edge_list.push_back(Edge(U, V, weight));
		}
		sort(edge_list.begin(), edge_list.end(), cmp);
		int sum_weight = 0;
		int edge_count = 0;
		for (int i = 0; i < edge_list.size(); i++)
		{
			Edge temp_edge = edge_list[i];
			if (findFather(temp_edge.U) == findFather(temp_edge.V))
			{
				continue;
			}
			else
			{
				unionFather(temp_edge.U, temp_edge.V);
				sum_weight = sum_weight + temp_edge.weight;
				edge_count++;
			}
			if (edge_count == N - 1)
			{
				break;
			}
		}
		cout << sum_weight << endl;
 

	}
}