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

题意其实就是给出了一个罪犯冲突网络，我们需要将一些罪犯分进两座*，以此删去一部分边。由于一名罪犯不可能即跟自己*里的狱友起冲突，又跟另一座*里的罪犯起冲突，所以显然这是一个二分图模型，即两部分内的罪犯各自不跟自己部分的罪犯起冲突（并不是两座*里的罪犯集）。

前面说到，我们的操作是删去一部分边，使最后权值最大的边最小，而又因为图需成立，所以显然删去边后我们需要保证图最终为二分图。

由于本题答案具备单调性，即如果任取一个界限 x x x，我们删去所有权值大于等于 x x x的边后，如果剩余图为二分图，则 x x x合法，显然我们可以尝试将 x x x“减小”（二分取左区间）一点，如果剩余图不为二分图，则 x x x非法，显然我们需要放松界限，让 x x x“增大”（二分取右区间）。

而上述二分步骤中的判定即二分图的判定，可以使用染色法来解决。染色法对访问过的节点染色，并对该点未染色的邻点染不同颜色，如果在任意执行过程中，有一个染色点的邻点中存在与其颜色相同的邻点，则显然不构成二分图。此处使用BFS实现上述染色判定，其中 3 − c o l o r 3-color 3−color求当前待涂颜色的小操作较有意思。

//
// Created by Visors on 2020/10/5.
//
// 题目名：P1525 关押罪犯
// 题目来源：noip2010
// 题目链接：https://www.luogu.com.cn/problem/P1525
// 算法：二分+二分图判定
// 用途：二分图判定
// 时间复杂度：O(TODO)
//

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge {
    int to, w, next;

    Edge() = default;

    Edge(int to, int w, int next) : to(to), w(w), next(next) {}
};

int n, m;

vector<Edge> edges;
vector<int> heads;
vector<int> colors;

inline void addEdge(int u, int v, int w) {
    edges.emplace_back(v, w, heads[u]);
    heads[u] = edges.size() - 1;
    edges.emplace_back(u, w, heads[v]);
    heads[v] = edges.size() - 1;
}

bool check(int x) {
    queue<int> q;
    fill(colors.begin(), colors.end(), 0);
    for (int i = 1; i <= n; i++) {
        if (colors[i]) continue;
        colors[i] = 1;
        q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int j = heads[u]; ~j; j = edges[j].next) {
                Edge &e = edges[j];
                int &v = e.to;
                if (e.w <= x) continue;
                if (colors[v] == 0) {
                    colors[v] = 3 - colors[u];
                    q.push(v);
                } else if (colors[v] == colors[u]) return false;
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    heads.resize(n + 1, -1);
    colors.resize(n + 1);
    int left = 0, right = 0, mid;
    for (int i = 1, a, b, c; i <= m; i++) {
        cin >> a >> b >> c;
        right = max(c, right);
        addEdge(a, b, c);
    }
    while (left < right) {
        mid = (left + right) >> 1;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    cout << right << endl;
    return 0;
}