「网络流 24 题」最小路径覆盖 题解

问题分析

最小路径覆盖问题是针对有向无环图(DAG)的经典问题，要求用最少的顶点不相交的简单路径覆盖图中所有顶点。每条路径可以从任意顶点开始，长度任意（包括0长度路径）。

算法思路

最小路径覆盖问题可以通过将其转化为二分图最大匹配问题来解决，核心结论是：最小路径数 = 顶点数 - 二分图最大匹配数。

转化方法如下：

1. 将原图中的每个顶点 $u$ 拆分为两个顶点 $u$（左部）和 $u'$（右部）
2. 对于原图中的每条有向边 $(u, v)$，在二分图中添加一条从左部 $u$ 到右部 $v'$ 的边
3. 求此二分图的最大匹配数 $m$
4. 最小路径覆盖数为 $n - m$

原理：每个匹配边对应将两个顶点合并到同一条路径，每增加一个匹配就减少一条所需路径。初始时每个顶点都是一条路径（共 $n$ 条），每匹配成功一对顶点就减少一条路径。

路径构造方法

在得到最大匹配后，需要还原具体的路径：

1. 对每个顶点 $u$，记录其匹配的顶点 $v$（即左部 $u$ 匹配右部 $v'$）
2. 找到所有没有前驱的顶点（即右部未被匹配的顶点）作为路径起点
3. 从起点开始，沿着匹配关系依次找到下一个顶点，直到没有匹配为止，形成一条路径

代码实现

使用匈牙利算法求解二分图最大匹配，然后根据匹配结果构造路径：

代码解释

1. 输入处理：读取顶点数 $n$ 和边数 $m$，构建邻接表
2. 匈牙利算法：
   • match_to[v] 记录右部节点 $v$ 匹配的左部节点
   • dfs 函数尝试为左部节点 $u$ 寻找可匹配的右部节点
   • 遍历所有左部节点，累计最大匹配数
3. 路径构造：
   • next_node[u] 记录节点 $u$ 的后继节点（根据匹配结果）
   • has_predecessor 标记节点是否有前驱，用于寻找路径起点
   • 从起点开始沿后继关系遍历，构建每条路径
4. 输出：依次输出每条路径和路径总数

样例解析

对于样例输入：

• 11个顶点，12条边
• 二分图最大匹配数为8
• 最小路径数 = 11 - 8 = 3
• 构造的3条路径分别为：1→4→7→10→11、2→5→8、3→6→9，与样例输出一致

该算法时间复杂度为 $O(nm)$，对于 $n \leq 200, m \leq 6000$ 的数据范围完全适用。