xxx 最小路径覆盖问题（二分图匹配应用） 题目描述 给定一个有向无环图（DAG），用最少的路径覆盖所有顶点，使得每个顶点恰好在一条路径上（路径可相交，但本问题通常要求不相交）。例如，若图有边 (1→2) 和 (2→3) ，则路径 1→2→3 可覆盖顶点1、2、3。目标是求最小路径数。 解题过程 问题转换思路 将原图G的每个顶点v拆成两个顶点：左部节点v_ x（代表起点）和右部节点v_ y（代表终点）。 对原图的每条边 (u→v) ，在二分图中添加边 (u_x → v_y) 。 最小路径覆盖数 = 原图顶点数 - 二分图最大匹配数。 转换原理解释 初始时，每个顶点自成一条路径，共n条路径。 若二分图中匹配一条边 (u_x → v_y) ，表示将u所在的路径与v所在的路径合并（u的后继是v），路径数减少1。 最大匹配数对应最大合并次数，因此最小路径数 = n - 最大匹配数。 构造二分图示例 设原图为DAG：边集 {(1→2), (2→3), (1→3)} ，顶点 {1,2,3} 。 构造二分图： 左部： {1_x, 2_x, 3_x} ，右部： {1_y, 2_y, 3_y} 。 边集： {1_x→2_y, 1_x→3_y, 2_x→3_y} 。 求二分图最大匹配 使用匈牙利算法： 从1_ x出发：匹配 (1_x, 2_y) 。 从2_ x出发：尝试匹配 (2_x, 3_y) （成功）。 从3_ x出发：无边可匹配。 最大匹配数为2。 计算最小路径覆盖 最小路径数 = 3 - 2 = 1。 验证：路径 1→2→3 可覆盖所有顶点。 算法步骤总结 a. 将原图顶点拆分为二分图的左右两部。 b. 根据原图边集构建二分图边。 c. 在二分图上求最大匹配（如用匈牙利算法）。 d. 最小路径数 = n - 最大匹配数。 e. 根据匹配结果还原路径：从无匹配的右部节点回溯，形成路径链。 关键点 该转换依赖DAG性质，确保路径无环。 实际路径可通过匹配关系反向追踪：右部未匹配点作为路径终点，沿匹配边反向遍历。