最小路径覆盖问题（DAG 上的二分图匹配解法） 题目描述 我们有一个有向无环图（DAG），图中每个顶点代表一个任务，每条有向边表示任务间的依赖关系（例如任务A必须在任务B之前完成）。 最小路径覆盖的目标是：用最少条不相交的路径（即路径之间不共享顶点）覆盖图中的所有顶点，使得每个顶点恰好出现在一条路径中。 示例 假设DAG包含顶点 {1,2,3,4} 和有向边 {(1,2), (2,3), (4,3)}。 一种可能的路径覆盖是两条路径：1→2→3 和 4。 这是最小的吗？如果我们用三条路径（每个顶点单独一条），可以覆盖但路径数更多。实际上最小路径覆盖数就是2，因为上述方案已无法用更少的路径覆盖所有顶点。 问题转换的关键思路 这是一个经典的图论问题，可以通过巧妙转换为二分图最大匹配来高效求解。转换方式如下： 将DAG的每个顶点拆成两个：一个“起点”顶点和一个“终点”顶点。 对于原图中的每条有向边 (u, v)，在二分图中从左部的“起点u”到右部的“终点v”连一条边。 在二分图上求最大匹配。 为什么这样转换有效？ 我们可以直观理解： 在原DAG中，一条路径可以看作一连串“连接”的顶点。 在拆分后的二分图中，一次匹配（一条边）就表示“将u作为v的前驱”，相当于在原路径中连接u和v。 初始时，每个顶点是独立的路径（n条路径）。 每增加一次匹配，就会将两条路径合并（通过连接前一条路径的尾部和后一条路径的头部），从而使总路径数减少1。 因此， 最大匹配数 = 可以合并的路径对数 。 最终的最小路径覆盖数公式为： 最小路径覆盖数 = 顶点总数 - 最大匹配数 解题步骤 我们通过一个具体例子来演示完整过程。 例子：DAG顶点为 {1,2,3,4}，有向边为 {(1,2), (1,3), (2,4), (3,4)}。 步骤1：构建二分图 将每个顶点i拆为左部顶点i（表示“作为路径起点”）和右部顶点i'（表示“作为路径终点”）。 对原图的每条有向边 (u, v)：在二分图中添加边 (u, v')。 本例的二分图边为：(1,2'), (1,3'), (2,4'), (3,4')。 步骤2：在二分图上求最大匹配 我们使用匈牙利算法（或其他二分图匹配算法）来求最大匹配。 过程如下： 从顶点1开始：尝试匹配1→2'，成功。 顶点2：尝试匹配2→4'，成功。 顶点3：尝试匹配3→4'，但4'已被匹配给2。于是检查4'的匹配点2能否改配：2尝试改到其他邻接点，但2只有邻接点4'，无法改配。因此3→4'匹配失败。 顶点3尝试匹配3→？它只有邻接点4'，已尝试失败。所以3无匹配。 顶点4：左部顶点4没有任何出边，所以无匹配。 最终最大匹配包含边 (1,2') 和 (2,4')，匹配数 = 2。 步骤3：计算最小路径覆盖数 最小路径覆盖数 = 顶点总数4 - 最大匹配数2 = 2。 这意味着我们至少需要2条不相交路径来覆盖所有顶点。 步骤4：从匹配构造路径覆盖方案 在二分图匹配中，匹配边 (u, v') 表示在原DAG中u是v的直接前驱。 我们可以从匹配信息反向构造路径： 收集匹配边：1→2' 和 2→4' 对应于原图边 (1,2) 和 (2,4)。 构造路径： 从顶点1开始，根据匹配1→2'，走到2；再根据匹配2→4'，走到4。得到路径1→2→4。 未被匹配的右部顶点3' 在原图中对应顶点3，它没有前驱匹配，所以是一条单独路径的起点。于是得到路径3。 因此两条路径为 {1→2→4, 3}，它们覆盖了所有顶点且不相交。 算法复杂度 二分图有 2n 个顶点，最多 m 条边（m 为原DAG边数）。 匈牙利算法复杂度为 O(√V * E)，V=2n，E=m，因此整体是 O(√n * m)。 关键思考 为什么这个转换只在DAG上有效？因为有向环会导致“合并路径”时可能形成环，而路径要求是无环的。DAG保证匹配构造的路径不会形成环。 这就是最小路径覆盖问题通过二分图匹配的经典解法，它将看似复杂的路径覆盖优化转化为可高效计算的最大匹配。