关押罪犯 （二分+二分图判定）

之前在洛谷上用并查集做过一次(但是显然我已经忘了怎么做了）。

对当前怨气值w进行判定，判断只用大于当前怨气值w的边进行二分图染色能否将原图分成两部分，剩下怨气值小于w的不用考虑，因为不会对当前答案造成影响。

不断二分找到最小的符合答案的w。

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    // cin.tie(0);                  \
    // cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 2e5 + 100;
const int maxm = 1e6 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
// int dis[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, -1, 1, 1, -1, 1, -1, -1};
// int m[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct Edge
{
    int next, to, w;
} e[maxn];
int head[maxn], col[maxn];
int n, m, k = 0;

void add(int u, int v, int w)
{
    e[k].next = head[u];
    e[k].to = v;
    e[k].w = w;
    head[u] = k++;
}
bool BFS(int s, int mid)
{
    queue<int> q;
    q.push(s);
    col[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = e[i].next)
        {
            int v = e[i].to;
            if (e[i].w <= mid)
                continue;
            if (col[v])
            {
                if (col[v] == col[u])
                    return false;
            }
            else if (col[v] == 0)
            {
                col[v] = 3 - col[u];
                q.push(v);
            }
        }
    }
    return true;
}
bool check(int mid)
{
    for (int i = 1; i <= n; i++)
        col[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (col[i] == 0)
        {
            if (BFS(i, mid) == false)
                return false;
        }
    }
    return true;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    IO;
    memset(head, -1, sizeof head);
    cin >> n >> m;
    int a, b, c;

    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    int L = 0, R = 1e9 + 10;
    int ans = 0;
    while (L <= R)
    {
        int mid = (L + R) >> 1;
        if (check(mid) == true)
        {
            ans = mid;
            R = mid - 1;
        }
        else
        {
            L = mid + 1;
        }
    }
    cout << ans;

    return 0;
}