分析

• 这一题相当于让我们求解：将图中的点分为两个集合，使得每个集合中的边权的最大值最小。

• 这一题可以使用二分来求解，二分的区间是$[0, 10^9]$，为什么可以使用二分来求解呢？因为答案具有二段性。

• 性质是：把边权值大于mid的边都保留，小于mid的边都删除，然后判断这个图是不是二分图。

• 对于答案右边的点，因为我们取得阈值更大了，保留的边会更少，答案都满足条件，因此答案右边的点都满足这个性质；答案左边的点都不满足这个性质，因为答案是所有符合条件中最小的一个。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[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] == c) return false;
    }

    return true;
}

bool check(int mid) {

    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i++)
        if (!color[i] && !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;
}