CSP-S 2023 第一轮 第36题：完善程序（第 19 题）第 3 空

题目

（第 $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(v);
        ++deg[v];
    }
    std::vector<int> Q;
    for (int i = 0; i < n; ++i)
        if (!deg[i]) Q.push_back(i);
    for (int i = 0; i < n; ++i) {
        int u = Q[i];
        for (int v : E[u]) {
            if (②)
                Q.push_back(v);
            --deg[v];
        }
    }
    std::reverse(Q.begin(), Q.end());
    for (int u : Q) {
        f[u] = 1;
        for (int v : E[u])
            f[u] = ③;
    }
    int u = next(Q, k);
    std::cout << u << std::endl;
    while (④) {
        ⑤;
        u = next(E[u], k);
        std::cout << u << std::endl;
    }
    return 0;
}

③处应填（）

选项

• A. std::min(f[u] + f[v], LIM)
• B. std::min(f[u] + f[v] + 1, LIM)
• C. std::min(f[u] * f[v], LIM)
• D. std::min(f[u] * (f[v] + 1), LIM)

答案

A

题解

选 A：std::min(f[u] + f[v], LIM)。

f[u] 表示从顶点 u 出发的路径数量。这些路径分为两类：

• 只包含 u 的路径：有 1 条，所以先令 f[u] = 1。
• 经过边 u → v 继续走的路径：每条从 v 出发的路径，前面加上 u，就得到一条从 u 出发的路径，因此贡献 f[v] 条。

所以递推式为： \[ f[u]=1+\sum_{v\in E[u]} f[v]. \]

程序已经用 f[u] = 1 计入了单点路径，循环中只需累加 f[v]，并将结果限制在 LIM： ``cpp f[u] = std::min(f[u] + f[v], LIM); ``

前面将拓扑序反转，是为了计算 f[u] 时，它所有后继 v 的 f[v] 都已经算好。