[題解]關押罪犯（并查集/二分圖判定）

又來水題了......

---

1.并查集：

我們想要盡量讓衝突值大的罪犯分到不同的監獄，所以自然按邊權排序

至於維護他們之間的關係，我們用帶擴展域的并查集

如果現在處理的兩個罪犯在同一監獄了，那麼他們一定是被迫安排的（為了避免更大的衝突值），所以這個衝突值一定是最小的

如果沒有的話，那麼就互相把對方加入自己的敵人集合里，把敵人的敵人和自己分別併在一起

（因為只有兩個監獄，所以敵人的敵人一定是和自己在同一監獄的）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=20010;
const int maxm=100010;
int n,m;
int fa[maxn],en[maxn];
struct node{
    int u,v,w;
}a[maxm];
int find(int x){
    while(x!=fa[x])x=fa[x]=fa[fa[x]];
    return x;
}
void unionn(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    fa[x]=y;
}
bool cmp(node a,node b){return a.w>b.w;}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        if(find(a[i].u)==find(a[i].v)){
            printf("%d",a[i].w);return 0;
        }
        else{
            if(!en[a[i].u])en[a[i].u]=a[i].v;//把敌人的敌人与自己分到同一组 
            else unionn(en[a[i].u],a[i].v);
            if(!en[a[i].v])en[a[i].v]=a[i].u;
            else unionn(en[a[i].v],a[i].u);
        }
    }
    printf("0");
}

2.二分圖判定

答案具有單調性，所以二分答案，把邊權大於mid的罪犯分到兩個不同的集合，在他們之間連邊，

因為只有兩個集合，每對點之間最多只有一條邊，所以符合二分圖的特點，於是染色法判二分圖，

是二分圖可行，縮小範圍，反之.

#include<bits/stdc++.h>
using namespace std;
const int maxn=20010;
const int maxm=100010;
struct node{
    int v,w,nxt;
}e[maxm*2];
int n,m,l,r,cnt,head[maxn];
void add(int u,int v,int w){
    e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}
bool bfs(int mid){
    queue<int>q;
    int col[maxn]={0};
    for(int i=1;i<=n;i++)
    if(!col[i]){
        q.push(i);
        col[i]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=head[x];i;i=e[i].nxt)
            if(e[i].w>=mid){
                if(!col[e[i].v]){
                    q.push(e[i].v);
                    if(col[x]==1)col[e[i].v]=2;
                    else col[e[i].v]=1;
                }
                else if(col[e[i].v]==col[x])return 0;
            }
        }
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        r=max(r,w);
        add(u,v,w);add(v,u,w);
    }
    r++;
    while(r>l+1){
        int mid=(l+r)>>1;
        if(bfs(mid))r=mid;
        else l=mid;
    }
    printf("%d",l);
}