最小路径覆盖问题（DAG 上的最小不相交路径覆盖与二分图匹配） 题目描述 给定一个有向无环图（Directed Acyclic Graph, DAG）\( G = (V, E) \)，我们需要用最少的不相交路径（即路径之间没有公共顶点）覆盖图中所有顶点。每条路径可以是单个顶点（长度为0的路径），也可以是经过若干条边的有向路径。目标是使路径条数最少。这就是 DAG 上的 最小路径覆盖问题 （Minimum Path Cover in a DAG）。 例如，一个 DAG 有三个顶点 A, B, C，边 A→B, B→C，那么可以用一条路径 A→B→C 覆盖所有顶点，路径数为 1。如果只有边 A→C，则至少需要两条路径：A→C 覆盖 A 和 C，B 单独作为一条路径，总路径数为 2。 解题过程 第一步：将问题转化为二分图最大匹配 关键思路：将 DAG 的每个顶点拆成两个点，分别放在二分图的左右两部分，然后通过边的关系建立二分图，从而将最小路径覆盖转化为二分图的最大匹配问题。 具体步骤： 构造二分图 \( B = (U, V, E') \)： 对 DAG 的每个顶点 \( x \)，在左部创建一个点 \( x_ {out} \)（表示“从 x 出发”），在右部创建一个点 \( x_ {in} \)（表示“进入 x”）。 对 DAG 的每条有向边 \( (u \to v) \)，在二分图中添加一条从 \( u_ {out} \) 到 \( v_ {in} \) 的边。 二分图的意义： 在二分图中选择一条边 \( (u_ {out}, v_ {in}) \)，对应于在原 DAG 中让路径从 u 走到 v（即 v 是 u 的后继）。 二分图的一个匹配表示：每个顶点最多有一个前驱和一个后继（因为匹配中每个点最多关联一条边）。 第二步：最小路径覆盖与最大匹配的关系 重要结论（Dilworth 定理的推广）： 最小路径覆盖数 = 顶点数 - 二分图最大匹配数 直观理解： 初始时，假设每个顶点单独成一条路径，路径数为 \( n \)（顶点数）。 每次在二分图中匹配一条边 \( (u_ {out}, v_ {in}) \)，相当于将 u 所在的路径和 v 所在的路径合并（因为 u 的后继是 v），从而减少一条路径。 所以最大匹配数 \( m \) 表示最多能合并的次数，因此最小路径覆盖数 = \( n - m \)。 第三步：算法步骤 输入 DAG \( G = (V, E) \)，顶点数 \( n = |V| \)。 构造二分图 \( B \)： 左部点集 \( L = \{1_ {out}, 2_ {out}, ..., n_ {out}\} \) 右部点集 \( R = \{1_ {in}, 2_ {in}, ..., n_ {in}\} \) 对每条边 \( (u, v) \in E \)，在 B 中添加边 \( (u_ {out}, v_ {in}) \)。 在二分图 B 上求最大匹配（例如用匈牙利算法或 Hopcroft-Karp 算法）。 设最大匹配的大小为 \( m \)，则最小路径覆盖数 = \( n - m \)。 （可选）根据匹配输出具体的路径覆盖方案。 第四步：输出具体路径的方案 从匹配结果可以构造路径： 初始化：每个顶点 \( i \) 为一个单独路径。 对匹配中的每条边 \( (u_ {out}, v_ {in}) \)，将 u 所在的路径和 v 所在的路径合并（注意方向：u 的路径末尾接上 v 的路径开头）。 实现时，可以记录每个顶点的“前驱”和“后继”，然后从没有前驱的顶点开始追踪路径。 第五步：示例 考虑 DAG 顶点为 {1, 2, 3}，边为 {1→2, 1→3, 2→3}。 构造二分图：左部 {1o, 2o, 3o}，右部 {1i, 2i, 3i}。 边：1o→2i, 1o→3i, 2o→3i。 求最大匹配：一种最大匹配是 {1o→2i, 2o→3i}，匹配大小 m=2。 最小路径覆盖数 = 3 - 2 = 1。 构造路径：从匹配得 1→2, 2→3，所以路径为 1→2→3，覆盖所有顶点。 第六步：正确性简要说明 二分图的匹配确保每个顶点在路径中最多有一个后继和一个前驱，从而形成不相交的路径集合。 匹配的每条边对应一次路径合并，因此最大匹配对应最多合并次数，得到最少路径数。 时间复杂度 ：构造二分图 O(|V|+|E|)，求最大匹配 O(√(|V|)|E|)（Hopcroft-Karp 算法）。