形式化题目

给出 $N$ 个点、$M$ 条带权无相边的图，边权 $c_j$ 表示两点间的怨气值。要把所有点划分成两个集合（两座监狱），一条边 $(a,b,c)$ 产生冲突当且仅当 $a,b$ 被分进同一个集合，冲突影响力为 $c$。

求一种划分方案，使得所有冲突的最大影响力最小，输出这个最小值；若不存在任何冲突则输出 $0$。

数据范围：$N \le 20000$，$M \le 100000$，$0 < c_j \le 10^9$。

正解

思路

朴素做法。 最直接的想法是枚举每个罪犯去哪座监狱（$2^N$ 种方案），对每种方案算出最大冲突影响力，取最小。$N \le 20000$ 时完全不可行，必须利用问题的特殊结构。

关键观察一：答案只由"某条边被迫同狱"决定。 设答案为 $x$，意味着：怨气值 $> x$ 的仇恨对都被成功分开了（同一座监狱里不存在这样的对），而某条怨气值为 $x$ 的边无法分开。反过来看，如果按怨气值从大到小处理仇恨对，尽量把每对都分到不同监狱，那么第一个"分不开"的对，它的怨气值就是答案——因为比它怨气值更大的对都已经处理完且没有冲突，市长看到的最大影响力恰好就是它。

关键观察二："分开所有怨气值大的对"本质是二分图判定。 把怨气值 $> x$ 的边全部保留，要求把点染成两色、每条边两端异色——这就是经典的二分图 2-染色问题。于是答案可以二分：判定"怨气值 $\ge x$ 的边构成的图是否是二分图"，随 $x$ 减小判定只会更容易，具有单调性。二分 + 每次染色是 $O(M \log C)$ 或 $O((N+M)\log M)$，已经可以过。但本题有更优雅、常数更小的写法：不开两座监狱反复染色，而是用并查集一次扫完。

扩展域并查集（“敌人的敌人是朋友”）。 把每个罪犯 $i$ 拆成两个域：

• $i$："$i$ 在第一监狱"这个身份；
• $i+n$："$i$ 在第二监狱"这个身份。

约束 “$a$ 与 $b$ 必须分居两狱” 翻译成两条合并：

• 合并 $a$ 与 $b+n$（$a$ 在一狱 $\Rightarrow$ $b$ 在二狱）；
• 合并 $b$ 与 $a+n$（$b$ 在一狱 $\Rightarrow$ $a$ 在二狱）。

一个并查集分量里所有"$a$ 或 $a+n$ 型"域是必须同时成立的绑定关系，所以 $find(a) = find(b)$ 就表示"$a$ 在一狱"与"$b$ 在一狱"被绑死了，即 $a,b$ 被迫同狱。

算法流程： 仇恨边按怨气值降序排序，逐条处理：

1. 若 $find(a) = find(b)$：这条边无法再分开，它的怨气值 $c$ 就是答案，直接输出（更大的边都已被合法安置，之后也不会产生更大的冲突）。
2. 否则合并 $a \sim b+n$、$b \sim a+n$，继续处理下一条。

所有边都处理完仍未冲突，说明图可以完全二分，答案为 $0$。

用样例走一遍。$n=4$，第一监狱域用 $1..4$ 表示，第二监狱域用 $1'..4'$（即 $5..8$）表示。边按怨气值降序处理，前三条都能安置：

步骤 3 之后，$2'$ 与 $3'$ 同分量、$4'$ 与 $1'$ 同分量；步骤 4 检查 $2$ 与 $3$ 时，$find(2)=1'$、$find(3)=4'$，而 $4'$ 已并入 $1'$ 所在分量——$2$ 和 $3$ 已被前面的大怨气值关系绑到同一座监狱，这条怨气值 $3512$ 的边无法满足，直接输出 $3512$，与样例一致。

这正体现了算法的正确性：输出的一定是降序扫描中第一条无法满足的边，比它大的边都已安置，因此这就是最大冲突的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 关押罪犯：扩展域并查集，按怨气值从大到小处理每条仇恨边。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll MAXN = 20005;

struct Edge {
    ll a, b, c;
};

Edge edges[MAXN * 5];
ll fa[MAXN * 2]; // 扩展域：1..n 第一监狱域，n+1..2n 第二监狱域

bool edge_greater(const Edge& x, const Edge& y) {
    return x.c > y.c;
}

// 路径减半的迭代式查根
ll find(ll x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    for (ll i = 0; i < m; i++) {
        scanf("%lld %lld %lld", &edges[i].a, &edges[i].b, &edges[i].c);
    }
    std::sort(edges, edges + m, edge_greater); // 怨气值降序

    for (ll i = 0; i <= 2 * n; i++) {
        fa[i] = i;
    }

    for (ll i = 0; i < m; i++) {
        ll a = edges[i].a, b = edges[i].b, c = edges[i].c;
        ll ra = find(a), rb = find(b);
        if (ra == rb) { // 冲突不可避免，c 即市长看到的最小最大值
            printf("%lld\n", c);
            return 0;
        }
        fa[ra] = find(b + n); // a 与 b+n 同盟 => a、b 分居两狱
        fa[rb] = find(a + n);
    }
    printf("0\n"); // 所有仇恨都能化解
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38"""
关押罪犯（ROJ 3122）：扩展域并查集，按怨气值从大到小处理边。

核心：二分图判定思想 —— "不能同狱"的关系要拆到两个集合里。
把每个罪犯 i 拆成 i(第一监狱域) 和 i+n(第二监狱域)。
怨气值降序处理每条仇恨边 (a,b,c)：
- 若 find(a) == find(b)：a、b 被迫同狱，c 就是答案（更大的 c 都已合法分配）。
- 否则合并 find(a)~find(b+n)、find(b)~find(a+n)（a、b 分居两狱）。
"""
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    # 仇恨边列表，怨气值降序
    edges = sorted(((next(data), next(data), next(data)) for _ in range(m)), key=lambda e: -e[2])

    # 扩展域：1..n 为第一监狱域，n+1..2n 为第二监狱域
    fa = list(range(2 * n + 1))

    def find(x: int) -> int:
        while fa[x] != x:
            fa[x] = fa[fa[x]]  # 路径减半
            x = fa[x]
        return x

    for a, b, c in edges:
        ra, rb = find(a), find(b)
        if ra == rb:  # 冲突不可避免，c 即市长看到的最小最大值
            print(c)
            return
        fa[ra] = find(b + n)  # a 与 b+n 同盟 => a、b 分居两狱
        fa[rb] = find(a + n)
    print(0)  # 所有仇恨都能化解


main()

复杂度

• 排序 $O(M \log M)$；并查集近似 $O(M\, \alpha(N))$（$\alpha$ 是阿克曼反函数，可视为常数）。总时间 $O(M \log M)$，对 $M \le 10^5$ 绰绰有余。
• 扩展域数组大小 $2N + 1$，空间 $O(N)$。

总结

• 答案 = 按怨气值降序扫描时第一条"无法分居"的仇恨边的怨气值；全部可分则答案为 $0$。
• "分居"约束用扩展域并查集表达：$i$ 与 $i+n$ 两个域，合并 $a \sim b+n$、$b \sim a+n$；$find(a) = find(b)$ 即被迫同狱。
• 正确性核心是单调性：大怨气值全部安置后，第一次失败处就是最优的最大冲突，无需二分。
• 对比另一常见写法（二分答案 + 染色判二分图），扩展域并查集一次排序加一次扫描即可，实现更短、常数更小。