题解 | #[NOIP2010]关押罪犯#

目标：影响力最大的冲突事件最小
常见思路：①贪心；②二分；③搜索、动态规划

贪心：先按照冲突从大到小排序，冲突大的先分开：对每个罪犯建两个点，表示他在A或B监狱。若两人分开，则 罪犯1在A监狱 与 罪犯2在B监狱 合并、1在B与2在A合并。如果后面想分开两人时，发现他们已经在同一集合中，则这个事件就是今年冲突最大的事件

#include <bits/stdc++.h>
using namespace std;
struct point{
    int x,y,nu;
}a[100010];
int comp(struct point p,struct point q){
    return p.nu>q.nu;
}
int fa[20010*2];
int find(int x){
    return (x==fa[x])?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=2*n;i++){
        fa[i]=i;
    }
    for(int i=0;i<m;i++){
        cin >> a[i].x >> a[i].y >> a[i].nu;
    }
    sort(a,a+m,comp);
    int i=0;
    for(;i<m;i++){
        if(find(a[i].x)!=find(a[i].y) && find(a[i].x+n)!=find(a[i].y+n)){//两人还没合并到同一监狱中
            merge(a[i].x,a[i].y+n);//x在监狱1，y在监狱2合并，这两件事具有相同真假性
            merge(a[i].x+n,a[i].y);//x在监狱2，y在监狱1合并，这两件事具有相同真假性
        }
        else{
            cout << a[i].nu << "\n";
            return 0;
        }
    }
    cout << "0\n" ;
    return 0;
}