关押罪犯

题目描述

S 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1 \sim N$。

冲突机制

我们使用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。

规则： 如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

报告机制

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。

公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

问题

警察局长准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

第一行为两个正整数 $N$ 和 $M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 $M$ 行每行为三个正整数 $a_j, b_j, c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。

数据保证： $1 \le a_j < b_j < N, 0 < c_j \le 10^9$ 且每对罪犯组合只出现一次。

输出格式

输出共 1 行，为 Z 市长看到的那个冲突事件的影响力。

如果本年内监狱中未发生任何冲突事件，请输出 $0$。

数据范围

• $N \le 20000$
• $M \le 100000$

输入样例

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出样例

3512

样例解释

输入数据

• $N = 4$：4名罪犯
• $M = 6$：6对仇恨关系

仇恨关系（怨气值从大到小排序）：

1. (1, 2): 28351
2. (3, 4): 12884
3. (1, 3): 6618
4. (2, 3): 3512
5. (1, 4): 2534
6. (2, 4): 1805

最优分配

我们需要将4名罪犯分配到两个监狱，使得同一监狱内的罪犯之间的最大怨气值最小。

方案：

• 监狱1：罪犯1和4
• 监狱2：罪犯2和3

检查冲突：

• 监狱1：罪犯1和4之间有怨气值2534 → 冲突事件影响力2534
• 监狱2：罪犯2和3之间有怨气值3512 → 冲突事件影响力3512
• 其他仇恨关系中的罪犯在不同监狱，不会冲突

冲突事件列表（按影响力从大到小）：3512, 2534, ...

Z市长看到第一个事件的影响力：3512

验证是否是最小值： 如果尝试其他分配：

• 监狱1：1和3（冲突6618）

• 监狱2：2和4（冲突1805） 市长看到的是6618 > 3512

• 监狱1：1和2（冲突28351）

• 监狱2：3和4（冲突12884）
  市长看到的是28351 > 3512

所以3512是最小可能的最大冲突值。

输出：3512

问题分析

转化为图论问题

将罪犯看作图中的顶点，仇恨关系看作边，怨气值就是边的权重。

我们需要将顶点分成两个集合（两个监狱），使得同一集合内的边的最大权重最小。

换句话说：删除一些边（这些边连接不同监狱的罪犯），使得剩下的边（同一监狱内的边）的最大权重最小。

二分答案

我们可以二分这个最大值 $X$：

判断条件： 是否存在一种分配方案，使得所有怨气值 $> X$ 的边连接的两个罪犯都在不同监狱（即这些边的两端不能在同一监狱）。

等价于： 对于所有怨气值 $> X$ 的边，它们构成一个图。我们需要判断这个图是否是二分图（即可以用两种颜色染色，使得每条边的两端颜色不同）。

二分图判定

如果一个图是二分图，那么可以用两种颜色给所有顶点染色，使得每条边的两端颜色不同。

判定方法：DFS或BFS染色

• 从任意顶点开始，染成颜色0
• 对于每条边，如果两端颜色相同，则不是二分图
• 如果成功染色所有顶点，则是二分图

算法步骤

1. 二分怨气值 $X$：$0$ 到最大怨气值之间
2. 验证：对于给定的 $X$，只考虑怨气值 $> X$ 的边，判断这些边构成的图是否是二分图
3. 寻找最小值：找到最小的 $X$ 使得验证通过

为什么正确

• 如果 $X$ 可行，那么所有怨气值 $> X$ 的边都不会在监狱内部出现
• 因此，监狱内部的最大怨气值不会超过 $X$
• Z市长看到的最大冲突值就是 $X$

算法实现

二分范围

• 下界：0（可能没有冲突）
• 上界：最大怨气值

验证函数

def check(mid):
    # 只考虑怨气值 > mid 的边
    构建图G，只包含怨气值 > mid 的边
    判断G是否是二分图
    返回True/False

二分查找

l, r = 0, max_weight
while l < r:
    mid = (l + r) // 2
    if check(mid):
        r = mid  # mid可行，尝试更小的值
    else:
        l = mid + 1  # mid不可行，需要更大的值
return l

时间复杂度

• 二分：$O(\log(\max(c)))$，最多约30次（$10^9$）
• 每次验证：需要遍历所有怨气值 $> mid$ 的边，构建图并染色
  • 构建图：$O(M)$
  • DFS/BFS染色：$O(N + M)$
• 总复杂度：$O((N+M) \log C)$，可以接受

示例详细验证（输入样例）

二分过程

最大怨气值：28351

第一次二分： $mid = (0 + 28351) // 2 = 14175$ 怨气值 > 14175 的边：只有 (1,2):28351 这个图只有一个边，是二分图（可以染色：1染0，2染1） 验证通过，$r = 14175$

第二次二分： $mid = (0 + 14175) // 2 = 7087$ 怨气值 > 7087 的边：(1,2):28351, (3,4):12884 图有两个不相连的边，是二分图 验证通过，$r = 7087$

第三次二分： $mid = (0 + 7087) // 2 = 3543$ 怨气值 > 3543 的边：(1,2):28351, (3,4):12884, (1,3):6618 图：1-2, 3-4, 1-3 尝试染色：

• 1染0，那么2染1，3染1（因为1-3边）
• 但3染1，4应该染0（3-4边） 染色成功，是二分图 验证通过，$r = 3543$

第四次二分： $mid = (0 + 3543) // 2 = 1771$ 怨气值 > 1771 的边：(1,2):28351, (3,4):12884, (1,3):6618, (2,3):3512, (1,4):2534 图更复杂，尝试染色... 可能不是二分图 验证失败，$l = 1772$

继续二分，最终找到最小值3512

边界情况

1. 没有冲突：输出0
2. 所有边都必须分开：输出最大怨气值
3. 可以完全避免冲突：输出0

优化

1. 排序：可以按怨气值从大到小排序，验证时只需要考虑前k条边
2. 并查集：也可以用带权并查集（扩展域并查集）解决，将每个罪犯拆成两个点：在监狱A和监狱B

扩展域并查集方法

每个罪犯 $i$ 拆成两个点：

• $i$：表示罪犯 $i$ 在监狱A
• $i+N$：表示罪犯 $i$ 在监狱B

对于每条边 $(a,b,c)$：

• 如果 $c > X$，那么 $a$ 和 $b$ 必须在不同监狱
  • 合并 $(a, b+N)$：如果a在A，则b在B
  • 合并 $(a+N, b)$：如果a在B，则b在A
• 检查矛盾：如果发现 $a$ 和 $a+N$ 在同一集合，则矛盾

这样可以避免显式建图，直接使用并查集判断。

时空限制

• 时间限制：1秒
• 空间限制：64MB