「NOI2010」航空管制-拓扑排序

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

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

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

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

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×