P5769 [JSOI2016] 飞机调度

题目描述

JSOI 王国里有 $N$ 个机场，编号为 $1$ 到 $N$。从 $i$ 号机场到 $j$ 号机场需要飞行 $T_{i,j}$ 的时间。由于风向，地理位置和航空管制的因素，$T_{i,j}$ 和 $T_{j,i}$ 并不一定相同。

此外，由于飞机降落之后需要例行维修和加油。当一架飞机降落 $k$ 号机场时，需要花费 $P_k$ 的维护时间才能再次起飞。

JS Airways 一共运营 $M$ 条航线，其中第 $i$ 条直飞航线需要在 $D_i$ 时刻从 $X_i$ 机场起飞，不经停，飞往 $Y_i$ 机场。

为了简化问题，我们假设 JS Airway 可以在 $0$ 时刻在任意机场布置任意多架加油维护完毕的飞机；为了减少飞机的使用数，我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。

JYY 想知道，理论上 JS Airways 最少需要多少架飞机才能完成所有这 $M$ 个航班。

输入格式

第一行包含两个正整数 $N$,$M$；

接下来一行包含 $N$ 个正整数表示每一个机场的飞机维护时间；

接下来 $N$ 行，每行 $N$ 个非负整数，其中第 $i$ 行第 $j$ 个非负整数为 $T_{i,j}$，表示从 $i$ 号机场飞往 $j$ 号机场所需要花费的时间。数据保证 $T_{i,i}=0$；

接下来 $M$ 行，每行三个正整数，其中第 $i$ 行为 $X_i,Y_i,D_i$，表示第 $i$ 条航线的起飞机场，降落机场，以及起飞时间。数据保证 $X_i\ne Y_i$。

输出格式

一行一个正整数，表示 JS Airways 理论上最少需要的飞机数。

输入输出样例 #1

输入 #1

3 3
100 1 1
0 1 1
1 0 5
2 1 0
1 2 1
2 1 1
3 1 9

输出 #1

2

输入输出样例 #2

输入 #2

3 3
100 1 1
0 1 1
1 0 5
2 1 0
1 2 1
2 1 1
3 1 8

输出 #2

3

说明/提示

样例说明1

在第一个样例中，JS Airways 可以在 $0$ 时刻在 $2$ 号机场安排一架飞机并执飞第 $2$ 条航线（$2\to 1$）。此外还需要在 $0$ 时刻在 $1$ 号机场安排一架飞机，这架飞机首先执飞第 $1$ 条航线（$1\to 2$），然后通过临时新增一条航线从 $2$ 号机场起飞飞往 $3$ 号机场，降落 $3$ 号机场之后执飞第 $3$ 条航线（$3\to 1$）。

样例说明2

在第二个样例中，执行完第 $1$ 条航线的飞机无法赶上第 $3$ 条航线的起飞时间，因此 JS Airways 必须使用 $3$ 架不同的飞机才能完成所有的航班。

数据范围

对于 $30\mathrm{\%}$ 的数据，满足 $N,M\le 10$；

对于 $60\mathrm{\%}$ 的数据，满足 $N,M\le 100$；

对于全部数据，满足 $1\le N,M\le 500$，$0\le P_i,T_{i,j}\le {10}^6$，$1\le D_i\le {10}^6$。

题解

把每条航线视作一个点，如果一架飞机在飞完第 $i$ 条航线后，能飞第 $j$ 条航线，就从 $i$ 向 $j$ 连一条有向边。显然会得到一个 DAG，我们的目标是用尽可能少的飞机飞完所有航线。这是一个 DAG 上的最小路径覆盖的模型。

现在问题来了，如何判断飞完第 $i$ 条航线后，是否能飞第 $j$ 条航线呢？

先用 Floyd 预处理从 $u$ 机场出发，到 $v$ 机场且具备起飞条件的最短时间 $f(u,v)$。

设第 $i$ 条航线的起点为 $x_i$，终点为 $y_i$，起飞时间为 $d_i$，则同一架飞机飞完第 $i$ 条航线后能飞第 $j$ 条航线，当且仅当 $d_i+t(x_i,y_i)+p_{y_i}+f(y_i,x_j)\le d_j$。