xxx 最小路径覆盖问题（二分图匹配应用）

题目描述
给定一个有向无环图（DAG），我们要求其最小路径覆盖。路径覆盖是指一个由简单路径组成的集合，使得图中的每个顶点恰好出现在一条路径中。最小路径覆盖则是包含路径条数最少的路径覆盖。

例如，一个有向图有5个顶点，边集为 {(1→2), (2→3), (4→5)}。一个可能的路径覆盖是 {1→2→3, 4→5}，它包含2条路径。我们需要找到覆盖所有顶点的最少路径数。

解题过程

1. 问题转化：关键思想
   这个问题的核心技巧是将原DAG转化为一个二分图。为什么可以转化？想象一条路径，它由一个起点和一些连续的边构成。在路径覆盖中，每个顶点要么是某条路径的起点，要么是另一个顶点的后继。我们可以将“顶点作为起点”和“顶点作为后继”这两种角色分离开。

   具体转化方法如下：

   • 将原DAG G中的每个顶点v拆分成两个顶点：vₓ（属于二分图左部）和vᵧ（属于二分图右部）。
   • 对于原图G中的每一条有向边 (u → v)，在二分图中为左部的uₓ和右部的vᵧ之间添加一条无向边。

2. 二分图建模
   经过上述转化，我们得到了一个二分图。这个二分图有什么意义？

   • 二分图中的一个匹配（一组边的集合，其中任意两条边没有公共顶点）对应了原图中的一个“边集合并”，并且这个边集合中的边不会有共享的顶点（即不会有一个顶点同时有两条入边或两条出边）。这正好对应了原图中我们可以“拼接”起来的一些路径片段。
   • 具体来说，如果我们在二分图中找到一条边 (uₓ, vᵧ)，它就对应原图中存在边 (u → v)。这意味着在覆盖路径中，顶点v紧跟在顶点u之后。

3. 路径数与匹配数的关系
   现在我们建立最小路径覆盖数和二分图最大匹配数之间的关系。

   • 设原图G有n个顶点。
   • 在最开始，最坏的情况下，我们为每个顶点都分配一条独立的路径。这样的路径覆盖包含n条路径。
   • 每当我们在二分图中找到一组匹配（即选择一条边），比如匹配了边 (uₓ, vᵧ)，其含义就是将原图中两条本独立的路径（一条以u结尾，一条以v开头）连接了起来。具体来说，u所在的路径和v所在的路径被合并成了同一条路径（... → u → v → ...）。
   • 每一次成功的匹配（即每连接两个路径片段），都会使总的路径条数减少1。因为两条路径合并成了一条。

   因此，如果我们能在二分图中找到一个大小为m的匹配，那么原图中的路径覆盖数就能从n减少到 n - m。

4. 核心公式与算法选择
   根据以上推理，我们得到了核心公式：
   最小路径覆盖数 = 原图顶点数 - 二分图最大匹配数

   所以，求解原图最小路径覆盖问题的步骤就非常清晰了：

   1. 构建二分图：将原DAG G的每个顶点v拆成vₓ和vᵧ。对于G中的每条边 (u → v)，在二分图中添加边 (uₓ, vᵧ)。
   2. 求最大匹配：在构建出的二分图上，使用经典的二分图最大匹配算法（例如匈牙利算法）求出其最大匹配数，设为M。
   3. 计算答案：根据公式，最小路径覆盖数 = n - M。

5. 实例演算
   让我们用开头的例子来验证：一个有5个顶点 {1,2,3,4,5}，边集为 {(1→2), (2→3), (4→5)} 的DAG。

   • 步骤1：构建二分图

     • 左部顶点：1ₓ, 2ₓ, 3ₓ, 4ₓ, 5ₓ
     • 右部顶点：1ᵧ, 2ᵧ, 3ᵧ, 4ᵧ, 5ᵧ
     • 根据边集添加无向边：(1ₓ,2ᵧ), (2ₓ,3ᵧ), (4ₓ,5ᵧ)

   • 步骤2：求最大匹配

     • 我们可以在二分图中找到一个大小为2的匹配。例如，匹配边 (1ₓ,2ᵧ) 和 (4ₓ,5ᵧ)。（注意：边 (2ₓ,3ᵧ) 无法再加入，因为顶点2ₓ和3ᵧ已经被使用了。实际上，最大匹配数就是2）。

   • 步骤3：计算答案

     • 最小路径覆盖数 = 5 (总顶点数) - 2 (最大匹配数) = 3。
     • 但是，我们之前直观的路径覆盖 {1→2→3, 4→5} 只用了2条路径。哪里出错了呢？

   • 分析与修正

     • 关键在于，我们的匹配边 (1ₓ,2ᵧ) 和 (4ₓ,5ᵧ) 对应的路径是 [1→2] 和 [4→5]。顶点3没有被任何匹配边覆盖！
     • 这意味着顶点3自己形成了一条独立的路径。所以最终的路径覆盖是 {1→2, 4→5, 3}，确实是3条路径。
     • 而我们直观想到的 {1→2→3, 4→5} 这个覆盖，对应在二分图中的匹配应该是怎样的？它应该包含边 (1ₓ,2ᵧ) 和 (2ₓ,3ᵧ)。这是一个大小为2的匹配吗？是的，并且这个匹配确实存在。让我们重新计算：
       • 最大匹配数 M = 2（通过选择边 (1ₓ,2ᵧ) 和 (2ₓ,3ᵧ)）。
       • 最小路径覆盖数 = 5 - 2 = 3？等等，还是3？但我们的路径是 {1→2→3, 4, 5}？不对，这样顶点4和5是独立的，路径覆盖是 {1→2→3, 4, 5}，一共3条。
     • 如何才能得到 {1→2→3, 4→5} 这个覆盖？它对应的匹配应该是边 (1ₓ,2ᵧ), (2ₓ,3ᵧ), (4ₓ,5ᵧ)。但这是一个大小为3的匹配。然而，在我们的二分图中，能同时选择这三条边吗？不能，因为边 (1ₓ,2ᵧ) 和 (2ₓ,3ᵧ) 都涉及了顶点2ₓ（它不能匹配两次），所以它们不能同时存在于一个匹配中。因此，最大匹配数M就是2。
     • 所以，{1→2→3, 4→5} 这个覆盖实际上对应着一种“匹配”关系，但这种关系在标准的二分图匹配中是不允许的（因为顶点2被用了两次）。因此，对于这个具体的图，最小路径覆盖数就是3。我们最初的直观感受是错误的，这个图确实需要3条路径才能覆盖所有顶点（例如 {1→2, 3, 4→5} 或 {1→2→3, 4, 5}）。

总结
最小路径覆盖问题通过巧妙的“拆点”建模，将问题转化为经典的二分图最大匹配问题。关键在于理解“每次匹配意味着两条路径的合并”，从而得出 最小路径覆盖数 = 顶点总数 - 最大匹配数 这一简洁而优美的结论。求解时，先构建二分图，再求最大匹配，最后代入公式即可。