CSP-S 提高级 · CSP 2023 提高级第一轮 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

1.

（第 $k$ 小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，定点编号从 $0$ 到 $n-1$，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 $1 \le n,m \le 10^5, 1 \le k \le 10^{18}$。

在程序中，我们求出从每个点出发的路径数量。超过 $10^{18}$ 的数都用 $10^{18}$ 表示。然后我们根据 $k$ 的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。

试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;
const long long LIM = 1000000000000000000ll;

int n, m, deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];

int next(std::vector<int> cand, long long &k) {
    std::sort(cand.begin(), cand.end());
    for (int u : cand) {
        if (①) return u;
        k -= f[u];
    }
    return -1;
}

int main() {
    std::cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v; // 一条从u到v的边
        E[u].push_back(

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是 DAG 上第 k 小路径。先拓扑排序逆序 DP 算出每个点出发的路径数（含自身），再按字典序贪心：若 k 小于等于当前点的路径数，就选它；否则 k 减去该路径数继续往后找。

最容易把 f[u] 算成只统计后继路径，忘记加 1（自身这条路径），导致起点判断出错；拓扑排序时误判入度为 0 的条件；while 循环里 k 减 1 的位置放错，或者 k>1 写成 k>=1 导致多输出一行；还有在 next 函数里判断不等号方向搞反，把 k<=f[u] 写成 k<f[u]，会漏掉刚好等于的情况。

这道题考什么

题目要求在有向无环图（DAG）中，找出所有简单路径里字典序第 k 小的那条路径。字典序比较路径序列：先比起点编号，起点相同再比下一个点，以此类推。因为 k 可以大到 10^18，直接枚举所有路径显然不行，必须用“统计 + 贪心”的思路。

核心概念人话版

1. 路径数统计：在 DAG 上，从某个点 u 出发能走出的简单路径总数，等于“只包含 u 本身的那条路径”加上“从 u 走到某个后继 v，再从 v 出发的所有路径”。也就是 f[u] = 1 + Σ f[v]。注意这个 1 很重要，很多同学会漏掉，以为 f[u] 只是后继路径的总和。 2. 拓扑排序：DAG 一定能按某种顺序排好，使得所有边都是从“前面的点”指到“后面的点”。程序里用经典的 Kahn 算法：不断删去入度为 0 的点，剩下的点依次加入队列。最后得到的 Q 数组就是拓扑序（从起点到终点）。 3. 贪心选点：既然知道从每个点出发有多少条路径，那要找第 k 小，就从字典序最小的点开始试：如果 k 小于等于该点的路径数，说明第 k 小就在以它为起点的那些路径里，直接选它；否则说明第 k 小在后面，就把 k 减去该点的路径数，继续试下一个点。

命题人怎么挖坑

• 坑 1：f[u] 的计算。代码里先初始化 f[u]=1，然后累加后继的 f[v]。如果写成 f[u] = min(f[u] + f[v], LIM) 就错了，因为这样只加了一个后继，漏掉了其他后继，导致总数不对。正确写法是遍历所有后继，每次加完再截断：f[u] = min(f[u] + f[v], LIM)。命题人特意把答案设为 A，就是考这个细节。
• 坑 2：拓扑排序的入度判断。在 Kahn 算法里，只有当 deg[v] == 0 时才能把它加入队列。如果写成 deg[v] == 1 或 deg[v] > 0，队列里就会混入还没处理完的点，后面的 DP 全乱套。答案 B 就是提醒这一点。
• 坑 3：起点选择的比较符号。函数 next 里，cand 是按编号排好序的。如果 k <= f[u]，说明第 k 小就在以 u 为起点的路径里，应该直接返回 u。很多同学会下意识想“k 小于 f[u] 才返回”，漏掉等于的情况，导致多减一次 f[u] 或者找不到起点。答案 B 就是这个微妙之处。
• 坑 4：while 循环的终止条件。输出当前节点后，如果 k=1，说明当前这条路径就是答案，不能再往下走了；如果 k>1，才需要继续找子路径。所以循环条件必须是 k > 1。写成 k > 0 会多输出一行，写成 k >= 1 也一样。答案 D 就是考这个边界。
• 坑 5：k 的递减位置。进入子节点前，要先“排除”当前节点本身作为一条完整路径的情况，所以 k 要减 1。这个减法必须放在输出当前节点之后、调用 next 之前。答案 C 就是这个操作。

拿到题先想什么→一步步推

1. 先算路径数：程序后半段用逆拓扑序（Q 反转后）做 DP。对每个 u，先把 f[u] 初始化为 1（代表只含 u 的路径），然后遍历它的出边 v，把 f[v] 加到 f[u] 上，同时用 LIM 截断。这就是空③的正确答案 A：min(f[u] + f[v], LIM)。 2. 找起点：用 next 函数，传入 Q（所有点按编号排好序）和当前的 k。next 内部把 Q 排序（其实已经排好，但为了安全），然后依次检查每个点 u：如果 k <= f[u]，说明第 k 小就在以 u 为起点的路径里，直接返回 u；否则 k -= f[u]，继续往后看。这就是空①的答案 B：k <= f[u]。 3. 输出起点：找到起点 u 后，先输出它，然后进入 while 循环继续构造后面的点。 4. while 循环逻辑： - 循环条件：k > 1（空④答案 D）。k=1 时当前路径就是答案，循环结束。 - 循环体第一步：--k（空⑤答案 C）。因为刚输出了当前节点，它本身也算一条路径，要把它从 k 里减掉，剩下的 k 才是子路径的序号。 - 第二步：调用 next(E[u], k)。E[u] 是 u 的出边邻接表，按字典序排好。next 会帮我们找到下一个点，同时更新 k。 - 第三步：输出找到的下一个点。 5. 验证边界：如果 k 刚好等于某点的路径数，next 会直接返回该点，不会减 k，这是对的。如果 k 大于该点路径数，next 会一路减完直到找到下一个点，也是对的。while 里的 --k 确保不会把已经输出的点再算进去。

避坑总结

• f[u] 一定要加 1：很多同学把 f[u] 算成 Σ f[v]，忘记自身这条路径，导致起点判断 k <= f[u] 永远不成立，程序直接输出 -1 或者跑偏。
• 拓扑排序的入度必须是 0：Kahn 算法里，只有入度为 0 的点才能进队列。如果误判，后面的 DP 顺序全错，f 值也就废了。
• next 里的不等号是 <=：k <= f[u] 时直接选 u，等于的情况不能漏。漏掉等于会导致多减一次，起点找晚一步。
• while 条件必须是 k > 1：k=1 时循环应该停止，否则会多输出一行。写成 k > 0 或 k >= 1 都会 WA。
• --k 的位置：必须在输出当前节点之后、调用 next 之前。放错位置会导致 k 减了但还没排除当前点，或者等 next 返回后再减，逻辑全乱。

考频与趋势

图的基本概念在题库中非常高频：共考过 281 题，覆盖 11 个考试级别。逐年分布显示，2023 年考了 36 题，2024 年 61 题，2025 年 58 题，2026 年 71 题，呈现明显的上升趋势。分赛事来看，GESP 八级和七级各 85 题，GESP 六级 27 题，CSP 提高级仅 13 题，说明图论在入门和中级阶段更受重视，提高级相对较少。

DFS（深度优先搜索）共 61 题，其中 2026 年考了 22 题，2025 年 9 题，2024 年 13 题，也是近年热点。拓扑排序相对冷门，全题库仅 8 题，但 2023 年考了 3 题，2025 年 1 题，说明在 DAG 相关题目中，拓扑排序作为预处理步骤依然常见。

预测

基于近年数据，图论在 CSP 提高级中的占比虽不高（13 题），但题目难度和综合性在提升，往往结合 DP、贪心、拓扑排序一起考。2024 和 2025 年图论题量激增，可能意味着命题人正在调整，未来几年图论在提高级中的比重有望回升。拓扑排序作为 DAG 的基础操作，大概率会继续作为子步骤出现在这类“第 k 小路径”“最长路径”“计数”等题目中。如果未来出现类似题目，建议复习拓扑排序的两种实现（Kahn 算法和 DFS 后序逆序），并强化 DAG 上 DP 的套路：先统计每个状态的可达数，再贪心或二分定位第 k 个。

暂无足够依据预测具体年份的考点，但整体趋势是图论 + DP + 贪心组合题会越来越常见，考生需扎实掌握 DAG 上的路径计数和拓扑序处理。