题目描述

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≤1000000000$ 且每对罪犯组合只出现一次。

样例

输入
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出
3512

算法1 –扩展域并查集

根据题意，如果要使发生冲突的影响力尽量小，就要让影响力大的事件尽可能避免，那么我们可以先对冲突事件按影响力从大到小
进行排序，针对每一个事件，如果可以避免(即这两个罪犯分别关押在两个监狱里),那么就安排下一个事件，如果不可避免，那么这
个事件的影响力就是答案，因为我们使从大到小排序的。

那么如何判断事件可避免和不可避免呢，这里可以用到扩展域并查集，对于罪犯i，p[i]表示罪犯i所属的监狱，p[i+n]表示罪犯i的敌人所在的集合，
那么如果事件不可避免的判断条件就是，某个罪犯的两个敌人关在了同一个监狱内。

关键就是敌人的敌人就是朋友！

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010, M = 100100;

int n,m;
int p[N*2];

struct node{
    int a,b,w;
    bool operator<(const node& x){
        return w>x.w;
    }
}e[M];

int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 1; i<=n*2; i++) p[i] = i;

    for(int i = 0; i<m; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[i] = {a,b,c};
    }
    sort(e,e+m);

    for(int i = 0; i<m; i++){
        int x = find(e[i].a),y = find(e[i].b);   //a和b在监狱x和y
        int opposite_x = find(e[i].a+n), opposite_y = find(e[i].b+n); //a和b的敌人所在的监狱
        if(x==y){   //两名罪犯关在同一个监狱内，冲突不可避免，直接输出答案
            printf("%d\n",e[i].w);
            return 0;
        }
        p[x] = opposite_y;  //a放在b的敌人的监狱中
        p[y] = opposite_x;  //b放在a的敌人的监狱中
    }
    printf("0\n");
    return 0;
}

算法2 –二分图判定+二分

使发生的冲突的影响力最小，那么可以考虑二分答案，对于每次二分的answer，我们只考虑权值大于answer的边，其他的边等价于删除，
如果剩下来的点和边可以构成二分图，即大于answer边的两个端点对应的罪犯安置在不同的监狱，那么返回true。

关于二分图判定，可以用染色法，可见y总基础课染色法判定二分图讲解。
写完看了y总代码，码风越来越接近y总了233

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010, M = 100100*2;  //无向边

int h[N],e[M],ne[M],w[M],idx;
int n,m;
int color[N];

void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

bool dfs(int u,int v,int res){
    color[u] = v;
    for(int i = h[u];~i; i = ne[i]){
        int j = e[i];
        if(w[i]<=res) continue;  //删除权值小于等于res的边
        if(!color[j]){
            if(!dfs(j,3-v,res)) return false; //将i的邻点染成2
        }else{
            if(color[j] == v) return false;  //染色发生冲突
        }
    }
    return true;
}

bool check(int x){
    //判定所有点以及权值大于x的边组成的图是否时二分图
    memset(color,0,sizeof color);
    for(int i = 1; i<=n; i++){
        if(!color[i]){
            if(!dfs(i,1,x))  //将i点染成1
                return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);

    memset(h,-1,sizeof h);
    for(int i = 0; i<m; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }

    int l = 0, r = 1e9;  //当罪犯间没有仇恨，ans为0，当仇恨最大为1e9时，关在一起ans最大

    while(l<r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid;
        else l = mid+1;
    }

    printf("%d\n",l);
    return 0;
}