Luogu P1954. [NOI2010] 航空管制

📝

内容提要

本文讨论了一个问题的解决方法，使用贪心算法求解每个点的最晚发车时间，并忽略传递闭包中的节点。

🎯

关键要点

• 第一问使用 DAG 动态规划求解每个点的真实最晚发车时间。

• 第二问仍然使用同一个动态规划数组，但在贪心构造时忽略所有询问点传递闭包里的节点。

• 代码实现中包含深度优先搜索（DFS）和反向深度优先搜索（RFS）来处理图的遍历。

• 通过排序和贪心策略来确定每个点的发车时间。

🏷️

标签

传递闭包 最晚发车时间 贪心算法