巧用二分图匹配：Python实现有向无环图最小路径覆盖问题求解

为了解决有向无环图（DAG）的最小路径覆盖问题，可以使用二分图匹配的方法。具体思路是将DAG的每个顶点拆分成两个顶点，分别放入二分图的左右两部分，然后通过寻找二分图的最大匹配，利用最小路径覆盖数等于顶点数减去最大匹配数的性质来求解。 下面是使用Python实现的代码： ```python from collections import defaultdict # 匈牙利算法求二分图最大匹配 def find_path(u, vis, match, graph): for v in graph[u]: if v not in vis: vis.add(v) if v not in match or find_path(match[v], vis, match, graph): match[v] = u return True return False # 计算最大匹配数 def max_match(graph, n): match = {} res = 0 for i in range(1, n + 1): vis = set() if find_path(i, vis, match, graph): res += 1 return res # 构建路径 def build_paths(match, n): paths = [] used = [False] * (n + 1) for i in range(1, n + 1): if not used[i]: path = [] cur = i while True: used[cur] = True path.append(cur) found = False for v in match: if match[v] == cur: cur = v found = True break if not found: break paths.append(path) return paths # 主函数 n, m = map(int, input().split()) graph = defaultdict(list) for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) # 计算最大匹配数 max_matching = max_match(graph, n) # 计算最小路径覆盖数 min_path_cover = n - max_matching # 构建路径 paths = build_paths({v: u for u, v in match.items()}, n) # 输出路径 for path in paths: print(" ".join(map(str, path))) # 输出最少路径数 print(min_path_cover) ``` 代码解释 1. 匈牙利算法求二分图最大匹配：`find_path` 函数用于寻找增广路径，`max_match` 函数通过不断调用 `find_path` 函数来计算二分图的最大匹配数。 2. 构建路径：`build_paths` 函数根据匹配结果构建路径，从每个未使用的顶点开始，沿着匹配边遍历，直到无法继续。 3. 主函数：读取输入，构建图，计算最大匹配数和最小路径覆盖数，构建路径并输出。 复杂度分析 - 时间复杂度：匈牙利算法的时间复杂度为 $O(nm)$，其中 $n$ 是顶点数，$m$ 是边数。 - 空间复杂度：主要用于存储图和匹配信息，空间复杂度为 $O(n + m)$。 ######[AI问答 | 714点数解答 | 2025-12-12 18:51:59]