xxx 最小路径覆盖问题（DAG 上的二分图匹配解法）

字数 2808 2025-12-07 02:39:55

xxx 最小路径覆盖问题（DAG 上的二分图匹配解法）

题目描述
给定一个有向无环图（DAG），我们定义一条“路径覆盖”为图中的一组不相交的路径，这些路径覆盖了图中的所有顶点（每个顶点恰好属于一条路径）。我们的目标是找到这样一个路径覆盖，使得路径的数量最少。这就是最小路径覆盖问题。
例如，一个 DAG 的顶点表示任务，有向边表示任务间的依赖（A→B 表示 A 必须在 B 之前完成），那么最小路径覆盖对应着最少需要多少条顺序链才能安排所有任务。我们需要设计一个算法，输入一个 DAG，输出其最小路径覆盖的大小（即最少路径数）。

解题过程
这个问题可以巧妙转化为二分图最大匹配问题，然后用匈牙利算法或 Hopcroft-Karp 算法求解。下面我们循序渐进地讲解。

1. 问题转化思路
在 DAG 中，一条路径是一串顺序相连的顶点。如果我们把每个顶点拆分成两个点：一个表示“作为路径的起点”（或说“从前一个点到达它”），另一个表示“作为路径的终点”（或说“它去往下一个点”）。
更具体地，对原 DAG 的每个顶点 \(u\)，我们创建两个点：左部点 \(u_{out}\)（表示从 \(u\) 出发的边）和右部点 \(u_{in}\)（表示进入 \(u\) 的边）。
然后，对于原 DAG 中的每条有向边 \(u \to v\)，我们在二分图中从左部点 \(u_{out}\) 向右部点 \(v_{in}\) 连一条边。
这样构造的二分图，其最大匹配就对应了原 DAG 中最多能“连接”起来的顶点对（每个匹配边 \(u_{out} \to v_{in}\) 表示在原路径中 \(u\) 后面是 \(v\)）。

2. 为什么这样转化能求最小路径覆盖？

初始时，每个顶点独自成一条路径，共有 \(n\) 条路径（\(n\) 为顶点数）。
每次在二分图中找到一个匹配，就相当于将两条路径合并：比如路径 \(P1: ... \to u\) 和路径 \(P2: v \to ...\)，如果存在边 \(u \to v\)，我们就可以通过这条边将两条路径连接成一条更长的路径，从而路径总数减少 1。
因此，最大匹配的边数 \(m_{max}\) 表示最多能合并的次数。合并后，最小路径覆盖的大小就是：

\[ \text{最小路径数} = n - m_{max} \]

因为初始有 \(n\) 条路径，每有一个匹配就减少一条路径。

3. 算法步骤
假设 DAG 有 \(n\) 个顶点，顶点编号为 \(1\) 到 \(n\)。
步骤 1：构造二分图

创建两个顶点集合 \(U = \{u_1, u_2, ..., u_n\}\) 和 \(V = \{v_1, v_2, ..., v_n\}\)，分别对应每个原顶点的“出点”和“入点”。
对 DAG 中的每条有向边 \((u, v)\)，在二分图中添加边 \(u_u \to v_v\)（即从 \(U\) 中的 \(u\) 到 \(V\) 中的 \(v\)）。
注意：这里 \(u_u\) 表示 \(U\) 中对应原顶点 \(u\) 的点，\(v_v\) 表示 \(V\) 中对应原顶点 \(v\) 的点。

步骤 2：求二分图最大匹配

在构造的二分图上运行匈牙利算法（或更快的 Hopcroft-Karp 算法）求最大匹配，设匹配边数为 \(m_{max}\)。
匈牙利算法流程回顾（用于理解）：
a. 初始化所有匹配为空。
b. 对左部每个点 \(u\)，尝试为它寻找增广路：从 \(u\) 出发，通过非匹配边、匹配边交替寻找一条到达未匹配右部点的路径，如果找到，则将路径上所有边的匹配状态取反（匹配变非匹配，非匹配变匹配），从而匹配数增加 1。
c. 重复直到没有增广路为止。

步骤 3：计算最小路径覆盖数

最小路径数 = \(n - m_{max}\)。

步骤 4（可选）：输出具体路径方案

根据最大匹配，我们可以还原出具体的路径覆盖：
a. 在匹配中，每条匹配边 \(u_u \to v_v\) 表示在原 DAG 中 \(u\) 的后继是 \(v\)。
b. 通过匹配边，我们可以链式地找出每条路径：从一个左部点 \(u_u\) 如果没有在匹配中作为“被指向”的点（即 \(u\) 在匹配中不是任何匹配边的终点），那么 \(u\) 就是某条路径的起点。然后沿着匹配边一直走到无法继续为止，就得到一条路径。
c. 收集所有这样的路径，就是最小路径覆盖的一个方案。

4. 举例说明
考虑一个 DAG 有 4 个顶点 {1,2,3,4}，边为：1→2, 1→3, 2→4, 3→4。

构造二分图：左部 {1,2,3,4}，右部 {1,2,3,4}，添加边：左1→右2, 左1→右3, 左2→右4, 左3→右4。
求最大匹配：一种最大匹配是 (左1→右2) 和 (左3→右4)，匹配数 \(m_{max}=2\)。
最小路径数 = 4 - 2 = 2。
还原路径：左2 被匹配到（作为右2），但左2 没有作为起点（即没有匹配边指向它），所以路径起点是 1→2→4；另一个路径起点是 3（因为左3→右4 的匹配中，3 没有被其他匹配边指向），但 4 已经被前一条路径覆盖，所以实际上 3 是单独一条路径？这里要小心：在还原时，我们看原顶点中，哪些点没有“入边”在匹配中（即右部点没有被匹配到），那么它就是路径起点。
匹配中右2匹配左1，右4匹配左3。所以右1、右3没有被匹配，对应原顶点1和3是路径起点。从1开始，匹配边 1→2，然后从2找匹配，2匹配到4吗？不对，匹配是 (左1→右2) 和 (左3→右4)，所以从1走到2后，2（作为左2）没有匹配边（因为它的匹配是作为右2被左1匹配，但左2自己没匹配出去），所以路径是 1→2；从3开始，匹配边 3→4，路径是 3→4。所以两条路径是 1→2 和 3→4，覆盖了所有顶点。
注意：这个例子中，因为1不能同时到2和3，所以最小路径数就是2。

5. 算法复杂度

二分图有 \(2n\) 个点，最多 \(m\) 条边（原 DAG 的边数）。
用匈牙利算法：\(O(n \cdot m)\)。
用 Hopcroft-Karp 算法：\(O(\sqrt{n} \cdot m)\)。
由于是 DAG，通常 \(m \le n^2\)，所以实际效率取决于图的大小。

6. 关键点总结

核心思想：将路径覆盖问题转化为二分图最大匹配，利用“路径合并”对应“匹配边”的关系。
公式：最小路径数 = 顶点数 - 最大匹配数。
该方法只适用于 DAG，因为如果有环，拆分后的二分图中可能形成循环依赖，导致匹配不能对应简单路径覆盖。
如果需要输出具体路径，可以通过匹配边关系反向追踪得到。

xxx 最小路径覆盖问题（DAG 上的二分图匹配解法）题目描述给定一个有向无环图（DAG），我们定义一条“路径覆盖”为图中的一组不相交的路径，这些路径覆盖了图中的所有顶点（每个顶点恰好属于一条路径）。我们的目标是找到这样一个路径覆盖，使得路径的数量最少。这就是最小路径覆盖问题。例如，一个 DAG 的顶点表示任务，有向边表示任务间的依赖（A→B 表示 A 必须在 B 之前完成），那么最小路径覆盖对应着最少需要多少条顺序链才能安排所有任务。我们需要设计一个算法，输入一个 DAG，输出其最小路径覆盖的大小（即最少路径数）。解题过程这个问题可以巧妙转化为二分图最大匹配问题，然后用匈牙利算法或 Hopcroft-Karp 算法求解。下面我们循序渐进地讲解。 1. 问题转化思路在 DAG 中，一条路径是一串顺序相连的顶点。如果我们把每个顶点拆分成两个点：一个表示“作为路径的起点”（或说“从前一个点到达它”），另一个表示“作为路径的终点”（或说“它去往下一个点”）。更具体地，对原 DAG 的每个顶点 \(u\)，我们创建两个点：左部点 \(u_ {out}\)（表示从 \(u\) 出发的边）和右部点 \(u_ {in}\)（表示进入 \(u\) 的边）。然后，对于原 DAG 中的每条有向边 \(u \to v\)，我们在二分图中从左部点 \(u_ {out}\) 向右部点 \(v_ {in}\) 连一条边。这样构造的二分图，其最大匹配就对应了原 DAG 中最多能“连接”起来的顶点对（每个匹配边 \(u_ {out} \to v_ {in}\) 表示在原路径中 \(u\) 后面是 \(v\)）。 2. 为什么这样转化能求最小路径覆盖？初始时，每个顶点独自成一条路径，共有 \(n\) 条路径（\(n\) 为顶点数）。每次在二分图中找到一个匹配，就相当于将两条路径合并：比如路径 \(P1: ... \to u\) 和路径 \(P2: v \to ...\)，如果存在边 \(u \to v\)，我们就可以通过这条边将两条路径连接成一条更长的路径，从而路径总数减少 1。因此，最大匹配的边数 \(m_ {max}\) 表示最多能合并的次数。合并后，最小路径覆盖的大小就是： \[ \text{最小路径数} = n - m_ {max} \] 因为初始有 \(n\) 条路径，每有一个匹配就减少一条路径。 3. 算法步骤假设 DAG 有 \(n\) 个顶点，顶点编号为 \(1\) 到 \(n\)。步骤 1：构造二分图创建两个顶点集合 \(U = \{u_ 1, u_ 2, ..., u_ n\}\) 和 \(V = \{v_ 1, v_ 2, ..., v_ n\}\)，分别对应每个原顶点的“出点”和“入点”。对 DAG 中的每条有向边 \((u, v)\)，在二分图中添加边 \(u_ u \to v_ v\)（即从 \(U\) 中的 \(u\) 到 \(V\) 中的 \(v\)）。注意：这里 \(u_ u\) 表示 \(U\) 中对应原顶点 \(u\) 的点，\(v_ v\) 表示 \(V\) 中对应原顶点 \(v\) 的点。步骤 2：求二分图最大匹配在构造的二分图上运行匈牙利算法（或更快的 Hopcroft-Karp 算法）求最大匹配，设匹配边数为 \(m_ {max}\)。匈牙利算法流程回顾（用于理解）： a. 初始化所有匹配为空。 b. 对左部每个点 \(u\)，尝试为它寻找增广路：从 \(u\) 出发，通过非匹配边、匹配边交替寻找一条到达未匹配右部点的路径，如果找到，则将路径上所有边的匹配状态取反（匹配变非匹配，非匹配变匹配），从而匹配数增加 1。 c. 重复直到没有增广路为止。步骤 3：计算最小路径覆盖数最小路径数 = \(n - m_ {max}\)。步骤 4（可选）：输出具体路径方案根据最大匹配，我们可以还原出具体的路径覆盖： a. 在匹配中，每条匹配边 \(u_ u \to v_ v\) 表示在原 DAG 中 \(u\) 的后继是 \(v\)。 b. 通过匹配边，我们可以链式地找出每条路径：从一个左部点 \(u_ u\) 如果没有在匹配中作为“被指向”的点（即 \(u\) 在匹配中不是任何匹配边的终点），那么 \(u\) 就是某条路径的起点。然后沿着匹配边一直走到无法继续为止，就得到一条路径。 c. 收集所有这样的路径，就是最小路径覆盖的一个方案。 4. 举例说明考虑一个 DAG 有 4 个顶点 {1,2,3,4}，边为：1→2, 1→3, 2→4, 3→4。构造二分图：左部 {1,2,3,4}，右部 {1,2,3,4}，添加边：左1→右2, 左1→右3, 左2→右4, 左3→右4。求最大匹配：一种最大匹配是 (左1→右2) 和 (左3→右4)，匹配数 \(m_ {max}=2\)。最小路径数 = 4 - 2 = 2。还原路径：左2 被匹配到（作为右2），但左2 没有作为起点（即没有匹配边指向它），所以路径起点是 1→2→4；另一个路径起点是 3（因为左3→右4 的匹配中，3 没有被其他匹配边指向），但 4 已经被前一条路径覆盖，所以实际上 3 是单独一条路径？这里要小心：在还原时，我们看原顶点中，哪些点没有“入边”在匹配中（即右部点没有被匹配到），那么它就是路径起点。匹配中右2匹配左1，右4匹配左3。所以右1、右3没有被匹配，对应原顶点1和3是路径起点。从1开始，匹配边 1→2，然后从2找匹配，2匹配到4吗？不对，匹配是 (左1→右2) 和 (左3→右4)，所以从1走到2后，2（作为左2）没有匹配边（因为它的匹配是作为右2被左1匹配，但左2自己没匹配出去），所以路径是 1→2；从3开始，匹配边 3→4，路径是 3→4。所以两条路径是 1→2 和 3→4，覆盖了所有顶点。注意：这个例子中，因为1不能同时到2和3，所以最小路径数就是2。 5. 算法复杂度二分图有 \(2n\) 个点，最多 \(m\) 条边（原 DAG 的边数）。用匈牙利算法：\(O(n \cdot m)\)。用 Hopcroft-Karp 算法：\(O(\sqrt{n} \cdot m)\)。由于是 DAG，通常 \(m \le n^2\)，所以实际效率取决于图的大小。 6. 关键点总结核心思想：将路径覆盖问题转化为二分图最大匹配，利用“路径合并”对应“匹配边”的关系。公式：最小路径数 = 顶点数 - 最大匹配数。该方法只适用于 DAG，因为如果有环，拆分后的二分图中可能形成循环依赖，导致匹配不能对应简单路径覆盖。如果需要输出具体路径，可以通过匹配边关系反向追踪得到。