31 Oct 2016 本文阅读量次

【CODEVS 1069】 关押罪犯

题目链接: 关押罪犯

思路

题目中的很多地方都在引导OIer使用 二分+二分图, 比如： 两座监狱, 求最大怨气值的最小值 等等, 这种方法虽然好想, 但是却不好写, 稍微处理不好就会超时。
正解是使用 并查集, 利用并查集的补集解题, 并查集不好想, 但时间和空间复杂度都比 二分+二分图 优很多。

并查集思路：

  • 根据 贪心 的思想, 我们将怨气值从大到小排序， 依次枚举， 我们尽量将两个罪犯分开到两个监狱， 实在分不开就只能输出当前怨气值， 如果最后还没退出程序， 就输出0。
  • 我们使用 并查集 维护这个过程， 使用并查集的补集来表示两个元素不在同一集合。
  • 如果 a和b不在同一集合, a和c不在同一集合, 那么 b和c一定在同一集合.

代码

/*
* Copyright © Eliot
* Date: 2016-10-31
* Author: Eliot
* QQ: 1161142536
* Description: 关押罪犯 并查集补集
*/

#include <iostream>
#include <cstdio> 
#include <algorithm>
using namespace std;

#define MAX 100001

int n = 0, m = 0;
int nFather[MAX] = { 0 };
struct STRUCT{
	int a, b, c;
	STRUCT() : a(0), b(0), c(0) {}
}P[MAX];

int cmp(const STRUCT A, const STRUCT B) {
	return A.c > B.c;
}

void Init() {
	for (int i = 1; i <= n * 2; i ++) {
		nFather[i] = i;
	}
}
int Find(int x) {
	if (nFather[x] != x) {
		nFather[x] = Find(nFather[x]);
	}
	return nFather[x];
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i ++) {
		scanf("%d %d %d", &P[i].a, &P[i].b, &P[i].c);
	}
	sort(P + 1, P + m + 1, cmp);
	
	Init();
	for (int i = 1; i <= m; i ++) {
		int nF_A = Find(P[i].a);
		int nF_B = Find(P[i].b);
		
		if (nF_A == nF_B) {
			cout << P[i].c << endl;
			return 0;
		}
		
		nFather[nF_A] = Find(P[i].b + n);
		nFather[nF_B] = Find(P[i].a + n);
	}
	
	cout << 0 << endl;
	return 0;
}
Tags:
Status:

Share:

Comments: