[NOIP 2010 提高组] 关押罪犯

GitHub跳转原题关系图返回列表

按怨气值从大到小加入异组约束，用 2N 并查集找第一条无法避免的冲突边。

OJ: luogu

题目 ID: P1525

难度:普及+/提高

标签:并查集二分图贪心排序python

日期: 2026-06-22 21:34

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

把 n 名罪犯分进两座监狱。若有怨气的一对罪犯同狱，就产生对应权值的冲突。求一种分法，使所有同狱冲突的最大权值最小。

思路

先把怨气边按权值从大到小处理。对当前边 (u,v,w)，希望 u,v 进入不同监狱，从而避免权值 w 的冲突。

使用 2n 个并查集节点表达两个相反阵营：x 是人物 x 所在侧，x+n 是其对立侧。要求 u,v 异组时：

  • 合并 u 与 v+n；
  • 合并 u+n 与 v。

处理一条边之前，若 find(u)==find(v)，说明此前权值更大的异组约束已经迫使两人同组，当前冲突无法避免。由于边按降序处理，这个 w 就是最小可能的最大冲突。

如果所有异组约束都能满足，则没有冲突，输出 0。

Python 知识

  • zip(data[2::3],data[3::3],data[4::3]) 把扁平整数按三元组重组为边。
  • sorted(...,key=lambda edge:-edge[2]) 按第三项权值降序排列。
  • Python 整数不会像 C++ int 一样溢出，本题权值可以直接比较。
  • 循环版并查集和按大小合并兼顾速度与递归安全。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：key 函数与降序排序。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：整数和递归差异。

代码

python
import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[:2]
    edges = sorted(zip(data[2::3], data[3::3], data[4::3]), key=lambda edge: -edge[2])

    parent = list(range(2 * n + 1))
    size = [1] * (2 * n + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    for u, v, weight in edges:
        if find(u) == find(v):
            print(weight)
            return
        union(u, v + n)
        union(u + n, v)

    print(0)


if __name__ == "__main__":
    main()

复杂度

排序需要 O(mlog⁡m)O(m\log m)，并查集操作为 O(mα(n))O(m\alpha(n))，总时间复杂度 O(mlog⁡m)O(m\log m)，空间复杂度 O(n+m)O(n+m)。

总结

最大值最小化带来“从大到小优先避免”的顺序。2N 并查集负责表达异组约束，第一次矛盾的位置就是答案。