拓扑排序
「NOI2010」航空管制-拓扑排序
· ✏️ 756 words · ☕ 2 mins read

假设目前被延误航班共有 n 个,编号为 1n 。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。

起飞序列还存在两类限制条件:

  • 第一类(最晚起飞时间限制):编号为 i 的航班起飞序号不得超过 ki ;

  • 第二类(相对起飞顺序限制):存在一些相对起飞顺序限制 (a,b) ,表示航班 a 的起飞时间必须早于航班 b ,即航班 a 的起飞序号必须小于航班 b 的起飞序号。

X 思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。