航空管制(弱化版) - 题目 - Universal Online Judge

题目描述

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

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

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

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

第一类（最晚起飞时间限制）：编号为$i$的航班起飞序号不得超过$k_i$。
第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制$(a,b)$，表示航班$a$的起飞时间必须早于航班$b$，即航班$a$的起飞序号必须小于航班$b$的起飞序号。

问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

第一行包含两个正整数$n$和$m$，$n$表示航班数目，$m$表示第二类限制条件（相对起飞顺序限制）的数目。

第二行包含$n$个正整数$k_1,k_2,\cdots,k_n$。

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

第二行包含$n$个整数$t_1,t_2,\cdots,t_n$，其中$t_i$表示航班$i$可能的最小起飞序号，相邻两个整数用空格分隔。


3 4 1 2 1

5 0
3 3 3 5 5


1 1 1 4 4

在样例$1$中：

起飞序列$3 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)$和$(3,1)$两个限制，航班$1$只能安排在航班$5$和$3$之后，故最早起飞时间为$3$，其他航班类似。

在样例$2$中：

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

对于$30\%$数据：$n\leq 10$。

对于$60\%$数据：$n\leq 500$。

对于$100\%$数据：$n\leq 2 \times 10^3,m\leq 10^4$。