题目重述

有 $N$ 个机场，$M$ 条已定航班，每条航班 $i$ 在 $D_i$ 时刻从 $X_i$ 起飞，直飞 $Y_i$（飞行时间 $T_{X_i,Y_i}$）。
飞机降落在 $k$ 号机场后，需要 $P_k$ 的维护时间才能再次起飞。
我们可以在 $0$ 时刻在任意机场放任意多架维护好的飞机，并且可以增开任意多条临时航线（即飞机可以从任意机场飞到任意机场，只要时间允许）。
问最少需要多少架飞机才能完成所有 $M$ 条航班。

思路分析

1. 问题本质

这是一个航班衔接问题：
一架飞机在执行完一个航班（或临时航线）降落后，经过维护时间，再飞一个临时航线到另一个机场，能否赶上下一个航班的起飞时间？

如果飞机在完成航班 $i$ 后，能通过一些临时飞行赶到航班 $j$ 的起飞机场并且不晚于 $D_j$，那么 $i$ 和 $j$ 可以由同一架飞机执行。

我们要最小化飞机数量，等价于用最少的飞机路径覆盖所有 $M$ 个航班，每个航班必须被一架飞机执行一次。

2. 转化为图论模型

把每个航班看作一个节点，共 $M$ 个节点。
对于两个航班 $i$ 和 $j$，如果飞机在完成 $i$ 后能赶到 $j$ 的起飞，则建立一条有向边 $i \to j$。

判断能否接上的条件：

• 航班 $i$ 在 $D_i$ 时刻从 $X_i$ 起飞，到达 $Y_i$ 的时间是 $D_i + T_{X_i,Y_i}$。
• 然后维护时间 $P_{Y_i}$，所以最早再次起飞时间是 $D_i + T_{X_i,Y_i} + P_{Y_i}$。
• 如果要从 $Y_i$ 飞到 $X_j$（$j$ 航班的起飞机场），需要时间 $T_{Y_i, X_j}$。
• 所以到达 $X_j$ 的时间是 $D_i + T_{X_i,Y_i} + P_{Y_i} + T_{Y_i, X_j}$。
• 这个时间必须 $\le D_j$（$j$ 航班的起飞时间），才能接上。

即： $ D_i + T_{X_i,Y_i} + P_{Y_i} + T_{Y_i, X_j} \le D_j $ 则 $i \to j$ 有边。

3. 最小路径覆盖

在有向无环图（DAG）中，最小路径覆盖数 = 节点数 - 最大匹配数（二分图匹配）。
这里我们的图不一定是 DAG，因为可能有时间循环
但注意：如果 $i \to j$ 有边，则 $D_j \ge D_i + \text{正数}$（因为 $T$ 和 $P$ 非负，且 $X_i \ne Y_i$ 和 $X_j \ne Y_j$ 以及机场不同，时间严格增加？不一定严格，因为 $P$ 可能为 0 且 $T$ 可能为 0 吗？$T_{a,a}=0$，但 $X_j \ne Y_j$，所以 $T_{Y_i,X_j}$ 可能为 0 吗？如果 $Y_i = X_j$，那么 $T_{Y_i,X_j} = 0$，所以可能 $D_j = D_i + T_{X_i,Y_i} + P_{Y_i}$，即可能相等，所以不是严格 DAG，但依然可以用二分图匹配做最小路径覆盖，因为匹配模型不要求 DAG，只要是有向图即可。）

方法：
将每个航班拆成两个点：左部 $u$ 和右部 $u'$。
如果原图有 $i \to j$ 的边，则在二分图中连接左部的 $i$ 和右部的 $j$。
求最大匹配 $m$，则最小路径覆盖 = $M - m$。

4. 为什么是最小路径覆盖

初始时，每个航班单独一架飞机（$M$ 条路径）。
如果匹配一条边 $i \to j$，意味着 $i$ 和 $j$ 由同一架飞机执行，路径数减少 1。
所以最小路径覆盖就是最少飞机数。

5. 实现细节

• 先用 Floyd 预处理机场间最短飞行时间（因为可以走临时航线，所以任意两机场 $a\to b$ 的最短时间 = $T_{a,b}$ 直接取，还是需要中转。题目允许临时航线，所以应该用 Floyd 计算任意两机场的最短飞行时间 $dist[a][b]$）。
• 那么判断 $i$ 到 $j$ 能否接上时，从 $Y_i$ 到 $X_j$ 的时间用 $dist[Y_i][X_j]$ 即可。
• 条件变为： $ D_i + T_{X_i,Y_i} + P_{Y_i} + dist[Y_i][X_j] \le D_j $
• 建二分图，跑最大匹配（匈牙利或 Dinic）。

6. 算法步骤

1. 读入 $N, M, P, T$。
2. 用 Floyd 计算 $dist[u][v]$ 表示 $u$ 机场到 $v$ 机场的最短飞行时间（初始 $dist[i][j] = T_{i,j}$）。
3. 读入 $M$ 个航班 $(X_i, Y_i, D_i)$。
4. 对每对航班 $(i, j)$，判断： $ D_i + T_{X_i,Y_i} + P_{Y_i} + dist[Y_i][X_j] \le D_j $ 成立则 $i \to j$ 有边。
5. 构建二分图，左部右部各 $M$ 个点，有边则连。
6. 求二分图最大匹配 $matchCount$。
7. 答案 = $M - matchCount$。

7. 复杂度

• Floyd: $O(N^3)$，$N \le 500$，可行。
• 建边: $O(M^2)$，$M \le 500$，可行。
• 匈牙利: $O(M \times E)$，最坏 $O(M^3)$，可行。