自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 22:55:41，当前版本为作者最后更新于2024-02-27 14:10:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解为官方题解。

首先确定对于一条路径：$E_1,E_2,E_3,...,E_k$ ，判断其是否为稳定路径的方法是：对于任意的 $E_x$ 与 $E_{x+1}(1 \le x <k)$ ，满足 $L_x \ge O_{x+1}$ 且 $R_x \le C_{x+1}$ ，即每条航道的到达时间区间必须被包含在下一条航道的开放时间区间内。

基于上面的结论，可以使用 BFS 的方法，在搜索过程中记录到达每个点的时间区间，再去寻找覆盖到达时间区间的出发航道，此过程是一个解决二维偏序的问题，可以使用暴力寻找二维偏序的方法做到 $O(n+m^2)$ 或 $O(n+md)$ ，其中 $d$ 为所有点的最大度数。

注意到题目还有另一个性质： $1 \le O_i,L_i \le 20$ ，可以使用多个 set 或单调栈的方法将二维偏序问题转化为一维偏序问题：对于每个点，将从该点出发的航道按照 $O_i$ 分别加入 $20$ 个以 $C_i$ 排序的 set 或单调栈中。在进行 BFS 的过程中，在经过一条航道 $k$ 后搜索下一条航道时，查询航道 $k$ 终点处所有 $O_i \le L_k$ 的数据结构中 $C_i \ge R_k$ 的航道，将它们全部取出数据结构并加入 BFS 的队列中即可。时间复杂度为 $O(m\log m)$ ，空间复杂度为 $O(20n + m)$，可以解决本题。