QQ扫一扫联系
(第 k 小路径)给定一张 n 个点 m 条边的有向无环图,定点编号从 0 到 n−1,对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。
求所有至少包含一个点的简单路径中,“路径序列”字典序第 k 小的路径。保证存在至少 k 条路径。上述参数满足 1≤n,m≤1015,1≤k≤1018。
在程序中,我们求出从每个点出发的路径数量。超过 1018的数都用 1018表示。然后我们根据 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; }
①处应填()
②处应填()
③处应填()
④处应填()
⑤处应填()
k >= f[u]
k <= f[u]
k > f[u]
k < f[u]
deg[v] == 1
deg[v] == 0
deg[v] > 1
deg[v] > 0
std::min(f[u] + f[v], LIM)
std::min(f[u] + f[v] + 1, LIM)
std::min(f[u] * f[v], LIM)
std::min(f[u] * (f[v] + 1), LIM)
u != -1
!E[u].empty()
k > 0
k > 1
K+=f[u]
k-=f[u]
--k
++k