还是畅通工程 （C++代码）

解题思路:

            还是并查集+快排

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
struct Node {
	int x, y, t;
}s[MAXN];
int N;
int f[MAXN];
bool cmp(Node a, Node b)
{
	return a.t < b.t;
}
int getf(int n)
{
	if (f[n] == n)
		return n;
	else
		return getf(f[n]);
}
int main()
{
	while (~scanf("%d", &N) && N)
	{
		int M = N * (N - 1) / 2;
		for (int i = 1; i <= M; i++)
			scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].t);
		sort(s + 1, s + M + 1, cmp);
		for (int i = 1; i <= N; i++)
			f[i] = i;
		int ans = 0;
		for (int i = 1; i <= M; i++)
		{
			int fx = getf(s[i].x), fy = getf(s[i].y);
			if (fx != fy)
			{
				f[fx] = fy;
				N--;
				ans += s[i].t;
				if (N == 1)
				{
					cout << ans << endl;
					break;
				}
			}
		}
	}
	return 0;
}