继续畅通工程 （C++代码）

解题思路:

                继续并查集+快排

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