#P1954. [NOI2010] 航空管制

    ID: 977 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>贪心2010NOI 系列Special Judge深度优先搜索DFS优先队列

[NOI2010] 航空管制

题目描述

世博期间,上海的航空客运量大大超过了平时,随之而来的航空管制也频频发生。最近,小 X 就因为航空管制,连续两次在机场被延误超过了两小时。对此,小 X 表示很不满意。

在这次来烟台的路上,小 X 不幸又一次碰上了航空管制。于是小 X 开始思考关于航空管制的问题。

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

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

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

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

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

输入格式

第一行包含两个正整数 nnmmnn 表示航班数目,mm 表示第二类限制条件(相对起飞顺序限制)的数目。

第二行包含 nn 个正整数 k1,k2,,knk_1,k_2,\cdots,k_n

接下来 mm 行,每行两个正整数 aabb,表示一对相对起飞顺序限制 (a,b)(a,b),其中 1a,bn1\leq a,b\leq n,表示航班 aa 必须先于航班 bb 起飞。

输出格式

第一行包含 nn 个整数,表示一个可行的起飞序列,相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案,输出任意一个即可。

第二行包含 nn 个整数 t1,t2,,tnt_1,t_2,\cdots,t_n,其中 tit_i 表示航班 ii 可能的最小起飞序号,相邻两个整数用空格分隔。

5 5
4 5 2 5 4
1 2
3 2
5 1
3 4
3 1

3 5 1 4 2
3 4 1 2 1

5 0
3 3 3 5 5

3 2 1 5 4
1 1 1 4 4

提示

样例解释

在样例 11 中:

起飞序列 3 5 1 4 23\ 5\ 1\ 4\ 2 满足了所有的限制条件,所有满足条件的起飞序列有:

$$\begin{aligned} 3\ 4\ 5\ 1\ 2\\ 3\ 5\ 1\ 2\ 4\\ 3\ 5\ 1\ 4\ 2\\ 3\ 5\ 4\ 1\ 2\\ 5\ 3\ 1\ 2\ 4\\ 5\ 3\ 1\ 4\ 2\\ 5\ 3\ 4\ 1\ 2 \end{aligned} $$

由于存在 (5,1)(5,1)(3,1)(3,1) 两个限制,航班 11 只能安排在航班 5533 之后,故最早起飞时间为 33,其他航班类似。

在样例 22 中:

虽然航班 4,54,5 没有相对起飞顺序限制,但是由于航班 1,2,31,2,3 都必须安排在前 33 个起飞,所以 4,54,5 最早只能安排在第 44 个起飞。

数据范围

对于 30%30\% 数据:n10n\leq 10

对于 60%60\% 数据:n500n\leq 500

对于 100%100\% 数据:n2×103,m104n\leq 2\times 10^3,m\leq 10^4

感谢 @FlierKing 提供 spj