题目链接:https://syzoj.com/problem/433
内存限制：128 MiB 时间限制：1000 ms
题目描述
S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为cj。数据保证1<=aj<bj<=N,0<cj<=1,000,000,000，且每对罪犯组合只出现一次。
输出格式
共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
样例输入
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出
3512
样例说明
罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 3512 （由 2 号和 3 号罪犯引发）。其他任何分法都不会比这个分法更优。
数据范围与提示
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
解题思路
用并查集表示每个犯人之间的关系，在同一个集合中则说明两人在同一个监狱，反之则不在同一个监狱。然后按照仇恨值的大小从大到小处理。对于每一组，先看两个人能不能加入不同的集合，如果可以，将两人加入不同的集合，如果不可以，则最大值就为该组仇恨值，输出。用补集来表示两个点不在一个集合中。如a和b在同一个集合中，则a和~b不在同一个集合中，不能把~b直接加入另一个集合，因为会对后面的结果产生影响。
如，3和4不在同一个集合中，但是我们现在不知道究竟是3在第一个监狱还是4在第一个监狱，所以此时用3和~4在同一个集合中来表示3和4不在同一个集合中。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct edge {
int a, b, c;
}e[100005];
int f[40005], n, m;
bool cmp(edge A, edge B) {
return A.c > B.c;
}
int getf(int u) {
if (f[u] != u)
return f[u] = getf(f[u]);
return u;
}
bool merge(int u, int v) {
int t1 = getf(f[u]);
int t2 = getf(f[v]);
if (t1 != t2) {
f[t1] = getf(v + n);
f[t2] = getf(u + n);
return false;
}
return true;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
int ans = 0;
for (int i = 0; i < m; i++)
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
sort(e, e + m, cmp);
for (int i = 1; i <= 2 * n; i++)
f[i] = i;
for (int i = 0; i < m && !ans; i++) {
if (merge(e[i].a, e[i].b)) {
ans = e[i].c;
}
}
printf("%d\n", ans);
}
return 0;
}
京公网安备 11010502036488号