最小路径覆盖问题（DAG 上的最小不相交路径覆盖与二分图匹配）
题目描述
给定一个有向无环图（DAG），我们需要找出若干条路径，使得这些路径覆盖图中所有顶点，且任意两条路径没有公共顶点（即顶点不相交）。我们的目标是最小化路径的数量。
这个问题被称为最小顶点不相交路径覆盖（Minimum Vertex-Disjoint Path Cover）。
注意：它不同于“最小边覆盖”或“最小点覆盖”，而是关注用尽可能少的、顶点互不相交的路径覆盖所有顶点。
核心思想：转化为二分图最大匹配
最小顶点不相交路径覆盖可以转化为二分图上的最大匹配问题来解决。
步骤概述：
- 将原 DAG 的每个顶点 \(u\) 拆成两个顶点：左部顶点 \(u_{\text{out}}\) 和右部顶点 \(u_{\text{in}}\)。
- 对于原图中的每条有向边 \(u \to v\)，在二分图中添加边 \(u_{\text{out}} \to v_{\text{in}}\)。
- 在这个二分图中计算最大匹配。
- 最小路径覆盖数 = 原图顶点数 − 最大匹配数。
为什么？
- 每个顶点最初单独成一条路径（n 条路径）。
- 如果有一条边 \(u \to v\)，则可以让 \(u\) 所在的路径和 \(v\) 所在的路径合并（即接在一起），从而减少一条路径。
- 在二分图中，一个匹配 \(u_{\text{out}} \to v_{\text{in}}\) 表示我们将顶点 \(u\) 所在的路径和顶点 \(v\) 所在的路径合并（u 的路径延伸去覆盖 v）。
- 每一次合并减少一条路径，所以最大匹配数 = 最多可合并的次数。
- 因此，最小路径数 = n − 最大匹配数。
解题步骤（实例演示）
输入
一个有向无环图，例如：
- 顶点集合：{1, 2, 3, 4}
- 有向边：{1→2, 1→3, 2→3, 2→4, 3→4}
图示：
1 → 2 → 4
↓ ↓
3 → 4
步骤 1：顶点拆分
每个顶点 i 拆成 i_out（左部）和 i_in（右部），得到二分图顶点：
左部集合 L = {1_out, 2_out, 3_out, 4_out}
右部集合 R = {1_in, 2_in, 3_in, 4_in}
步骤 2：根据原边添加二分图的边
原边 1→2 → 二分图边 1_out → 2_in
原边 1→3 → 二分图边 1_out → 3_in
原边 2→3 → 二分图边 2_out → 3_in
原边 2→4 → 二分图边 2_out → 4_in
原边 3→4 → 二分图边 3_out → 4_in
注意：没有自环或反向边，因为原图是 DAG。
步骤 3：在二分图中求最大匹配
我们用匈牙利算法（或 Hopcroft–Karp 算法）求最大匹配。
可能的匹配（一种）：
- 匹配 1_out → 2_in
- 匹配 2_out → 3_in
- 匹配 3_out → 4_in
这里匹配大小为 3。
步骤 4：由匹配构造路径覆盖
初始：每个顶点单独成路径： [1], [2], [3], [4]
匹配 1_out→2_in 表示 1 的路径延伸到 2，合并为 [1→2], [3], [4]
匹配 2_out→3_in 表示 2 的路径延伸到 3，由于 2 已在路径 [1→2] 中，合并得 [1→2→3], [4]
匹配 3_out→4_in 表示 3 的路径延伸到 4，合并得 [1→2→3→4]
最终只有一条路径覆盖所有顶点。
验证公式：最小路径数 = 4（顶点数）− 3（最大匹配数） = 1。正确。
详细算法实现
- 构造二分图邻接表 bipart_adj：
for u in 1..n:
for v in adj[u]: # 原图 u→v
添加边 u_out → v_in - 在 bipart_adj 上运行二分图最大匹配算法（匈牙利或 Hopcroft–Karp）。
- 设最大匹配数为 m，则最小路径覆盖数 = n − m。
- 若要输出具体路径，可以根据匹配数组 match[u_in] = v_out 的关系反向追踪：
- 先找到所有路径的终点（在右部未被匹配的顶点对应的原顶点）。
- 从终点沿匹配边向左回溯，直到无法回溯为止，得到一条路径。
思考
- 如果原图有环，这个方法还能直接用吗？
不能，因为环会导致二分图匹配产生“循环”，可能无法形成简单路径覆盖。不过，我们可以先求强连通分量缩点，在 DAG 上做，但此时路径覆盖是 SCC 级别的。 - 如果允许路径有公共顶点（点可重复），就是“最小边不相交路径覆盖”，需要用最大流解决。
- 本方法也可用于 DAG 的“最小链覆盖”，是 Dilworth 定理的一个应用。
复杂度
- 建二分图：O(V+E)
- 匈牙利算法：O(V·E)（稠密图适用）
- Hopcroft–Karp 算法：O(E√V)（更高效）
因此总复杂度取决于所选匹配算法。