关押罪犯（二分图）

关押罪犯

题意

有 n n n个人，他们之间有 m m m对关系，每对关系有一个值。现在有两间房子，要把这些人安置在这两间房子里。问这两间房子中的关系最大值的最小值是多少。

数据范围

n ≤ 20000 n \leq 20000 n≤20000
m ≤ 100000 m \leq 100000 m≤100000

思路

要求最大值最小，首先考虑二分答案。两间房子可以看成是两个要素，因此判断一下是否是一个二分图即可（不满足条件的边忽略）。

代码

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

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
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 c,int mid)
{
    color[u] = c;
    for(int i=h[u];~i;i=ne[i]){
        int j = e[i];
        if(w[i]<=mid) continue;
        if(!color[j]){
            if(!dfs(j,3-c,mid)) return false;
        }
        else if(color[j]==color[u]) return false;
    }
    return true;
}

bool check(int mid)
{
    memset(color,0,sizeof(color));
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1,mid)) return false;
        }
    }
    return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c), add(b,a,c);
    }
    int l = 0, r = 1e9;
    while(l<r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n",r);
    return 0;
}