第 19 题 1. （第 k 小路径）给定一张 n 个点 m条边的有向无环图，定点编号从 0到n−1，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一

1.

（第 kk 小路径）给定一张 n 个点 m条边的有向无环图，定点编号从 0到n−1，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 k小的路径。保证存在至少 k 条路径。上述参数满足 。WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

在程序中，我们求出从每个点出发的路径数量。超过 的数都用  表示。然后我们根据 kk 的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

试补全程序。WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. #include <iostream> 
2. #include <algorithm> 
3. #include <vector> 
4.  
5. const int MAXN = 100000; 
6. const long long LIM = 1000000000000000000ll; 
7.  
8. int n, m, deg[MAXN]; 
9. std::vector<int> E[MAXN]; 
10. long long k, f[MAXN]; 
11.  
12. int next(std::vector<int> cand, long long &k) { 
13.     std::sort(cand.begin(), cand.end()); 
14.     for (int u : cand) { 
15.         if (①) return u; 
16.         k -= f[u]; 
17.     } 
18.     return -1; 
19. } 
20.  
21. int main() { 
22.     std::cin >> n >> m >> k; 
23.     for (int i = 0; i < m; ++i) { 
24.         int u, v; 
25.         std::cin >> u >> v; // 一条从u到v的边 
26.         E[u].push_back(v); 
27.         ++deg[v]; 
28.     } 
29.     std::vector<int> Q; 
30.     for (int i = 0; i < n; ++i) 
31.         if (!deg[i]) Q.push_back(i); 
32.     for (int i = 0; i < n; ++i) { 
33.         int u = Q[i]; 
34.         for (int v : E[u]) { 
35.             if (②) 
36.                 Q.push_back(v); 
37.             --deg[v]; 
38.         } 
39.     } 
40.     std::reverse(Q.begin(), Q.end()); 
41.     for (int u : Q) { 
42.         f[u] = 1; 
43.         for (int v : E[u]) 
44.             f[u] = ③; 
45.     } 
46.     int u = next(Q, k); 
47.     std::cout << u << std::endl; 
48.     while (④) { 
49.         ⑤; 
50.         u = next(E[u], k); 
51.         std::cout << u << std::endl; 
52.     } 
53.     return 0; 
54. } 

1. ①处应填（）WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2. ②处应填（）WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3. ③处应填（）WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4. ④处应填（）WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

5. ⑤处应填（）WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
    WU3100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库