QQ扫一扫联系
(第k小路径)给定一张n个点m条边的有向无环图，顶点编号从0到n-1对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n,m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
①处应填()
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
