【题解】继续畅通工程

题目：继续畅通工程

题意:

给定n个点，n*(n-1)/2条边，每个边标记是否已经在集合中，问从剩余的边中加入集合得到最小生成树的代价。

思路：

首先我们想到可以用prim或者kruskal，因为具体某些边可能已经被标记了，所以用kruskal更方便。那么怎么去处理被标记的边呢？并查集又一次展现了它的强大魅力 ，我们可将被标记的边加入集合，那么就可以很简单的处理标记和不标记边的区别了。

ps:

不知道是不是我们学校vj的问题，在结构体里重载运算符居然判编译错误…

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<set>
#include<map>

using namespace std;

const int N = 10010, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
typedef long long ll;

int n;
int p[N];
struct ss
{
	int a, b, c, d;
/*	bool operator<(const ss& s)
	{
		return c < s.c;
	}*/
}s[N];

bool cmp(ss a, ss b)
{
	return a.c < b.c;
}
int find(int x)
{
	if (p[x] == x)return x;
	else return p[x] = find(p[x]);
}

int main()
{
	while (cin >> n && n > 0)
	{
		memset(s, 0, sizeof s);
		for (int i = 1; i <= n; ++i)p[i] = i;
		int m = n * (n - 1) / 2;

		for (int i = 0; i < m; ++i)
		{
			cin >> s[i].a >> s[i].b >> s[i].c >> s[i].d;
		}

		int sum = 0;
		for (int i = 0; i < m; ++i)
		{
			if (s[i].d)
				p[find(s[i].a)] = find(s[i].b);//合并区间
		}

		sort(s, s + n * (n - 1) / 2, cmp);
		for (int i = 0; i < m; ++i)
		{
			if (!s[i].d)
			{
				int a = find(s[i].a), b = find(s[i].b);
				if (a != b)//说明不在同一个集合中
				{
					p[a] = b;
					sum += s[i].c;
				}
			}
		}

		cout << sum << endl;
	}

	return 0;
}