## 题目描述 给定有向图 。设 是 的一个简单路（顶点不相交）的集合。如果 中每个定点恰好在 的一条路上，则称 是 的一个路径覆盖。 中路径可以从 的任何一个定点开始，长度也是任意的，特别地，可以为 。 的最小路径覆盖是 所含路径条数最少的路径覆盖。设计一个有效算法求一个 DAG（有向无环图） 的最小路径覆盖。 ## 输入格式 第一行有两个正整数 和 。 是给定 DAG（有向无环图） 的顶点数， 是 的边数。接下来的 行，每行有两个正整数 和 表示一条有向边 。 ## 输出格式 从第一行开始，每行输出一条路径。文件的最后一行是最少路径数。 ## 样例 #1 ### 样例输入 #1 ``` 11 12 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 11 10 11 ``` ### 样例输出 #1 ``` 1 4 7 10 11 2 5 8 3 6 9 3 ``` ## 提示 对于 的数据， ， 。

为了解决有向无环图（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)$。 [2025-12-12 18:51:59 | AI问答 | 714点数解答]