网络流模型 · 最小路径覆盖 & 拓展

Linge_Zzzz · 2024-04-26 10:47:09 · 个人记录

定义

在一个 DAG（有向无环图中），选择其中的一些简单路径，若图中每个点都恰好在其中一条路径上，则称这些路径是一个路径覆盖。

所有路径覆盖中，路径条数最小的路径覆盖叫做最小路径覆盖。

例如在上图中，\{\{1\},\{2,3\},\{4,5\}\} 是一个路径覆盖，\{\{1,2,3,4,5\}\} 是一个最小路径覆盖，只用了一条路径。

任务是找出 DAG 上的最小路径覆盖，且输出方案。

建模

考虑二分图最大匹配。

我们对原图中每个点 u 拆成两个点，记为左部点 L(u) 和右部点 R(u)。

对于原图中每条边 (u,v)，连接 L(u) 到 R(v)。

则答案为原图中点数减去最大匹配数。

正确性

假设开始时图上的每个点都自成一条路径，我们要做的是尽可能多地把路径合并。

考虑一下路径合并的隐藏条件：

首先，路径合并是可以传递的，简单来说，如果 x 能跟 y 合并，y 能跟 z 合并，那么 \{x,y,z\} 可以合并成一条路径。所以我们可以只考虑点与点之间的合并关系，再利用传递性求方案。

其次，每条路径只能向一个路径合并，也只能被一条路径合并。

这下就好办了。在我们构造的二分图中，如果一条边 (L(u),R(v)) 被选中了，那么说明在原图中点 u 要向点 v 合并，同时其它在二分图中与其它 L(u) 相连的边都不能被选中，对应着在原图中一个点仅能选择另外一个点进行合并。

此时的最大匹配就是可以合并的数量，用总的点数减去它就是答案。

至于方案数，可以根据上面所说的，用并查集简单维护即可。

二分图的最大匹配我们可以选择用最大流来求。跑完最大流后，如果一条连接 L(u) 和 R(v) 的边容量为 0，则说明这条边在二分图中被选中了。

拓展 1 · 最小链覆盖

所谓最小链覆盖，无非是把路径改为了链。对应的，DAG 上的每一个点可以被重复覆盖多次。

此时我们对 DAG 用 Floyd 进行传递闭包，得出每个点相互可不可达，再根据这个跑最小路径覆盖即可。

拓展 2 · DAG 最大独立集

顾名思义，我们要在 DAG 中选取一些点，使得任意两个点都不能从其中一个点到另外一个。

此时我们引入偏序集。

偏序集

偏序集和偏序关系

我当然不会上来就放形式化的东西，否则你们还有什么来看的必要呢？

所谓偏序集，指的是一个集合和一个关系的共同体。

那么何为关系？举个最简单的例子，“\leq”（小于等于号）是一个关系。

现在我们给偏序集做一个定义，百度说：

若在集合 A 上给定一个偏序关系 \leq ，则称集合 A 按偏序关系 \leq 构成一个偏序集合，集合 A 和偏序 \leq 一起称为偏序集，记作 (A,\leq)。

不懂。什么是偏序关系？

设 R 是集合 A 上的一个关系，如果 R 是自反的、反对称的和可传递的，则称 R 是集合 A 的偏序关系，简称偏序，记作“\leq”。

现在对偏序关系中的一些名词做一些解释：

自反：\forall a\in A,a\leq a

反对称：\forall a,b\in A, 若 a\leq b 且 b\leq a, 则 a=b

传递性：\forall a,b,c\in A, 若 a\leq b 且 b\leq c, 则 a\leq c

不妨把这个小于等于号真的当做一个小于等于号来看待，则 \leq 是 \mathbb{R} 的偏序关系。

所以我们可以说 (\mathbb{R},\leq) 是一个偏序集。

元素之间的可比关系

设 (P,\leq) 是一个偏序集。