flag

「网络流 24 题」魔术球

题解

最小路径覆盖

参考:最小路径覆盖问题 - BYVoid

定义

对于有向图 $G= (V, E)$,设 $P$ 是 $G$ 的若干 简单路径 构成的集合,若 $$\forall v\in V, \exists! p\in P, v\in p$$ 则称 $P$ 是 $G$ 的一个路径覆盖.$G$ 的包含最少路径的路径覆盖称为 $G$ 的最小路径覆盖.
值得注意的是,简单路径的长度可以为 $0$,即只含一个点.

求解

给定有向无环图 $G$,如何求其最小路径覆盖? 构造一个二分图,对于原图 $G$ 中的每个顶点 $u$,在二分图的两个点集 $X, Y$ 中分别建点 $x_u, y_u$;对于原图 $G$ 中的每条边 $(u, v)$,在二分图中连边 $(x_u, y_u)$,则 $x_u, y_u$ 分别对应了原图中定点 $u$ 作为路径上一条边的始边和终边的情形.原图无环,因此该二分图的一个匹配一定对应了原图 $G$ 的一个路径覆盖,所有匹配边对应了原图中所有属于路径覆盖中路径的边.

可以证明,原有向无环图的最小路径覆盖包含的路径数 = 原图的顶点数 - 此二分图的最大匹配数.
考虑二分图一个匹配 $M$ 中的每条匹配边 $(x_u, y_v)$,对应了该匹配对应的原图的路径覆盖 $P$ 中的某条路径上存在边 $(u, v)$.因此,对于 $P$ 中的一条路径的起点 $v$,对应的 $M$ 中一定不存在边 $(x_u, y_v)$,反之亦成立.因此,二分图的点集 $Y$ 中,不是匹配点的点的数量即为该匹配对应的 $P$ 中路径起点的数量.每条路径有且只有一个起点,所以该数量等同于 $|P|$.显然 $Y$ 中匹配点的数量等于匹配边的数量,所以 $|P| = |Y| - |M|$.根据二分图的构造方式,有 $$|P| = |V| - |M|$$ 其中 $M$ 是路径覆盖 $P$ 对应的二分图匹配.因而,二分图的最大匹配对应了原图的最小路径覆盖,从而上命题得证.

求解时,只需要构造二分图,求二分图匹配即可.
输出所有路径时,考虑最大匹配的每条匹配边 $(x_u, y_v)$,对应了对应的最小路径覆盖中一条路径上的边 $(u, v)$,因此可以枚举最大匹配的每条匹配边 $(x_u, y_v)$,记录前驱 $prev(v) = u$ 和后继 $next(u) = v$,然后枚举原图中的所有顶点,发现不存在前驱的点时,便找到了路径覆盖中一条路径的起点,不断找后继即可输出这条路径,从而可以输出所有路径.

构图与实现

如果用 $n$ 个柱子放下 $1..m$ 的所有球,我们对于 $1..m$ 的每个球建点,根据题目中的约束条件,可以对于所有 $u < v\wedge u + v \in N^2$ 的 $(u, v)$ 建边,该图的包含 $n$ 条路径的路径覆盖即对应了一种放球的方案.因此,对于 $1..m$ 的球建图,该图的最小路径覆盖包含的路径数即是需要用到的最少的柱子数量.记该值为 $f(m)$,答案就是 $max\left \{ m|f(m) \leq n \right \}$.
$f(m)$ 随 $m$ 非严格单调递增,因此可以二分答案.更优的做法是枚举答案,因为数据范围很小,我们可以通过在 $m = k$ 时构造的图上增加点和边得到 $m = k + 1$ 时对应的图,并可以通过继续增广得到新图的最大匹配,节省了二分答案时重新构图和重新从零流开始增广消耗的时间.

实现时遇到了两个坑:

  • 由于本题会多次加边,每次进行 Dinic 时并非从零流开始增广,因而需要用全局变量维护最大流.
  • 有的路径只含一个点,所以最大匹配可能没有匹配到所有球.

代码

loj6003_flow24.cpp