NOIP2010关押罪犯

题目描述

$S$S 城现有两座监狱，一共关押着 $N$N 名罪犯，编号分别为 $1-N$1−N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$c 的冲突事件。每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是少？

输入

第一行为两个正整数 $N和M$N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 $M$M 行每行为三个正整数 $a_j，b_j，c_j$aj​，bj​，cj​，表示 $a_j$aj​ 号和 $b_j$bj​ 号罪犯之间存在仇恨，其怨气值为 $c_j$cj​。数据保证，且每对罪犯组合只出现一次。

输出

共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

样例输入

$46$4  6
$142534$1  4  2534
$233512$2  3  3512
$1228351$1  2  28351
$136618$1  3  6618
$241805$2  4  1805
$3412884$3  4  12884
（数据经过latex最好不要复制，我只是觉得不加latex有点难看）

样例输出

$3512$3512

提示

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件

影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。

【数据范围】

对于30%的数据有 $N\le 15$N≤15。

对于70%的数据有 $N\le 2000，M\le 50000$N≤2000，M≤50000。

对于100%的数据有 $N\le 20000，M\le 100000$N≤20000，M≤100000。

分析

要冲突值最小，肯定要先将冲突值从大到小排序，然后一个个将冲突双方放入不同监狱，直到无法再放，此时冲突值即为 $ans$ans。问题就在于，什么时候能把双方放入不同监狱呢？这时候就要用到并查集了。这道题很像NOI2001食物链，属于种类并查集的题目。

做法

原则：敌人的敌人就是朋友。处理 $a和b$a和b这对冲突时，有两种情况：
①：如果 $a和b$a和b已经在同一阵营，冲突显然不可避免，于是直接输出冲突值
②： $a,b$a,b不在同一阵营，就要把 $a$a放入 $b$b敌人的阵营， $b$b放入 $a$a敌人的阵营
问题在于怎么表示 $a,b$a,b的敌人的阵营呢？
把数组开大一倍，用 $b+n$b+n表示 $b$b的敌人就可以了。每次找 $b$b敌人的阵营，直接 $find(b+n)$find(b+n)就可以了。

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100003
struct node{
	int a, b, c;
	bool operator < (const node & A) const{
		return c > A.c;
	}
}d[N];
int f[N];
int find(int x){
	return x == f[x]? x: f[x] = find(f[x]);
}
int main(){
	int i, j, n, m, a, b;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; i++){
		scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);
	}
	sort(d + 1, d + i);
	for(i = 1; i <= 2 * n; i++) f[i] = i;
	for(i = 1; i <= m; i++){
		a = find(d[i].a); b = find(d[i].b);
		if(a == b){
			printf("%d", d[i].c);
			return 0;
		}
		f[a] = find(d[i].b + n);
		f[b] = find(d[i].a + n);
	}
	printf("0");
	return 0;
}