D1T1

览遍千秋 · 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)，可以解决本题。