题解

思路分析

【方法1】二分答案+染色二分图

题目中有明显的求最大值最小的概念，于是可以考虑二分答案，对于最大值检查可以采用二分图染色。

【方法2】贪心+并查集（带权/扩展域名）

由于题目的答案一定是其中的某一条边长，怎么使得该边长最小？ 可以想到每次先将较大值放入不同监狱，如果可以放置，那么后面的答案一定更小；如果不能放置，则其就是答案。

所以可以按照边长排序，降序合并每条边即可。

合并的时候有两种策略

1. 带权并查集：使用权值来维护当前元素与根节点元素的种类关系，如 d[u]=0表示 u与root是同类，d[u]=1表示不同类。带权并查集的find和union操作需要适当更新权值数组d[u]；

int find(int u) {
    if (u != p[u]) {
        int fu = p[u];
        p[u] = find(p[u]);
        d[u] = (d[u] + d[fu]) % 2;
    }
    return p[u];
}
void union_(int u, int v) {
    int a = find(u), b = find(v);
    p[a] = b;
    d[a] = ((d[v] - d[u] + 2) % 2 + 1) % 2;
}

2. 扩展域并查集：将并查集的规模扩展为原来的两倍，前一半用于维护朋友关系，后一半用于维护敌人关系。如 (u,u+n) 是敌人，(v,v+n) 是敌人，当 (u,v)是敌人的时候，根据敌人的敌人是朋友，可以将 u 与 u的敌人(v)的敌人(v+n)合并，即合并 (u, v+n)；同理合并 (v, u+n)。

程序实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, p[N << 1], d[N << 1];
struct T {
    int u, v, w;
    bool operator<(const T& t) const { return w < t.w; }
} g[M];

// -------------------
// 二分答案+染色二分图
vector<int> G[N];
int color[N], flag;
void dfs(int u, int c) {
    color[u] = c;
    for (auto v : G[u]) {
        if (!color[v]) dfs(v, ~c);
        else if (color[v] == c) flag = 0;
    }
}
bool chk(int k) {  // 将边权 >k 的建图，检查是否可以进行二分图染色
    for (int i = 1; i <= n; i++) G[i].clear();
    for (int i = k + 1; i <= m; i++) {
        int u = g[i].u, v = g[i].v;
        G[u].push_back(v), G[v].push_back(u);
    }
    flag = 1, memset(color, 0x00, sizeof color);
    for (int i = 1; i <= n && flag; i++)
        if (!color[i]) dfs(i, 1);
    return flag;
}
int solve1() {
    int l = 0, r = m, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        chk(mid) ? r = mid - 1, ans = mid : l = mid + 1;
    }
    return g[ans].w;
}
// -------------------
int find(int u) {
    if (u != p[u]) {
        int fu = p[u];
        p[u] = find(p[u]);
        d[u] = (d[u] + d[fu]) % 2;
    }
    return p[u];
}
// 带权并查集
// d[i]表示 i与根节点的关系：0-朋友，1-敌人
int solve2() {
    for (int i = 0; i <= n; i++)
        p[i] = i, d[i] = 0;
    for (int i = m; i >= 1; i--) {
        int u = g[i].u, v = g[i].v;
        int a = find(u), b = find(v);
        if (a == b && (d[u] - d[v] + 4) % 2 == 0)
            return g[i].w;
        p[a] = b;
        d[a] = ((d[v] - d[u] + 2) % 2 + 1) % 2;
    }
    return 0;
}
// 扩展域并查集
// 敌人的敌人是朋友:u,u+n是敌人，u,v是敌人，将u放入v的敌人v+n的集合
int solve3() {
    for (int i = 0; i <= n * 2; i++)
        p[i] = i;
    for (int i = m; i >= 1; i--) {
        int u = g[i].u, v = g[i].v;
        int a = find(u), b = find(v);
        if (a == b)
            return g[i].w;
        p[a] = find(v + n);
        p[b] = find(u + n);
    }
    return 0;
}
int main() {
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w, g[i] = {u, v, w};
    sort(g + 1, g + 1 + m);

    // cout << solve1() << endl;//AC
    // cout << solve2() << endl;//AC
    cout << solve3() << endl;  // AC
    return 0;
}