洛谷 P1525 关押罪犯（算法竞赛进阶指南， 并查集，贪心）

算法竞赛进阶指南，261页，并查集，贪心
本题要点：
1、贪心：
先把所有的边从大到小排序，然后依次将边的两个点分到不同的两监狱中。
（越大的怒气值的一组罪犯应分在两个不同的监狱里）
如果选到某一条边，这条边的两个端点恰好在同一个集合中，说明这条边的长度就是答案。
2、使用并查集：
扫描每条边，两个端点（假设两个点为a, b点）位于不同的监狱中，这两个点互为敌人;
如果a点有敌人(enemy[a] != 0)，说明之前a点已经被分配到某个监狱了, 那么b点应该加入 enemy[a] 所在的集合;
如果a点没有敌人(enemy[a] == 0)，说明之前a点是第一次扫描到, 令 enemy[a] = b;
b点类似处理;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 20010;
const int MaxM = 100010;
int n, m;
int fa[MaxN], enemy[MaxN];		//数组 enemy[i] 记录第i点的敌人struct rec
{
    int x, y, z;bool operator< (const rec& rhs) const{
    return z > rhs.z;}
}edge[MaxM];int get(int x)
{
    if(fa[x] == x)return x;return fa[x] = get(fa[x]);
}void merge(int x, int y)
{
    fa[get(x)] = get(y);
}void solve()
{
    for(int i = 1; i <= n; ++i){
    fa[i] = i;}sort(edge + 1, edge + m + 1);int a, b, ans = 0;for(int i = 1; i <= m; ++i){
    a = edge[i].x, b = edge[i].y;		int fa_a = get(a), fa_b = get(b);if(fa_a == fa_b){
    ans = edge[i].z;break;}if(enemy[a])	//如果 a有敌人，将b和a的敌人关在同一个监狱{
    merge(b, enemy[a]);}else{
    			enemy[a] = b;}if(enemy[b])	//如果 b有敌人，将a和b的敌人关在同一个监狱{
    merge(a, enemy[b]);}else{
    			enemy[b] = a;}}printf("%d\n", ans);
}int main()
{
    int x, y, z;scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i){
    scanf("%d%d%d", &x, &y, &z);edge[i].x = x, edge[i].y = y, edge[i].z = z;}solve();return 0;
}/* 4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 *//* 3512 */