RainAir
My OI Blog
RainAir
「NOI2010」航空管制

题目描述

题目链接
有 $n$ 个航班依次起飞,一个时刻只能有一个飞机起飞,并且有 $m$ 个限制:
1. 第一种限制,第 $i$ 个飞机必须在 $c_i$ 的时刻前起飞。
2. 第二种限制,第 $i$ 个飞机必须在第 $j$ 个飞机之前起飞。
询问:
1. 一个可行的起飞方案。
2. 每个飞机最早的起飞时间。
$ n \leq 2 \times 10^3, m \leq 10^4$

题解

首先这是一道十分套路的反图拓扑排序。
举例:如果想求出一张有向图中标号 $x$ 的节点最靠前的拓扑序,怎么求?
显然不能开个堆直接跑,这是字典序最小的不保证 $x$ 在最前面,但是我们如果建出反图在反图跑最大字典序的话,就一定能让 $x$ 尽量朝后,答案就是把这个反图拓扑序列 reverse 一下。
那么对于第一问,我们按照第二种限制建出反图,显然第一种的每个限制就变成了每一个航班在拓扑序中的位置 $ pos >n-c_i $,然后按照第一种限制将节点扔到小根堆里跑一边拓扑排序最后 reverse 一下就可以了。
对于第二问,我们考虑在反图中遍历到 $x$ 节点的时候,一直等到有一个约束失效的时候在让 $x$ 入队,这样就能保证 $x$ 尽量靠后(reverse 后尽量靠前)。
时间复杂度瓶颈在于第二种询问,为 $O(n^2)$

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/280
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOI2010」航空管制
题目描述 题目链接 有 $n$ 个航班依次起飞,一个时刻只能有一个飞机起飞,并且有 $m$ 个限制: 1. 第一种限制,第 $i$ 个飞机必须在 $c_i$ 的时刻前起飞。 2. 第二种限制,第 $i$ 个飞机…
扫描二维码继续阅读
2018-11-21
标签
近期评论