③处填写什么()
给定一张n个点 m 条边的有向无环图,顶点编号从0到n-1。对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少 k条路径,上述参数满足1<=n,m<=10^5 和1<=k<=10^18表示 .在程序中,我们求出从每个点出发的路径数量。超过10^18的数都用 10^18表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。 试补全程序。
#include <iostream>
#include<algorithm>
#incTude <vector>
const int MAXN = 100000;
const long long LIM =10000000000000000001l
int n,m,deg[MAXN];
std::vector<int> E[MAXN];
long 1ong k,f[MAXN];
int next(std::vector<int> cand, 1ong long &k) {
std::sort(cand.begin0,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;
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::end1;
}
return 0;
}
std::min(f[u]*(f[v]+ 1),LIM)
std::min(f[u]+f[v]+1,LIM)
std::min(f[u]* f[v],LIM)
std::min(f[u]+ f[v],LIM)