P9466 [EGOI 2023] Bikes vs Cars / 骑车与汽车

Day 1 Problem D. 题面译自 [EGOI2023 bikesvscars](https://egoi23.se/assets/tasks/day1/bikesvscars.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

在隆德，骑自行车是一种常见的交通方式，但有时狭窄的街道难以容纳汽车和自行车通行。为了改善这一状况，当地政$ $府希望完全重新设计当地的街道网络。 隆德共有 $N$ 个关键位置（编号从 $0$ 到 $N-1$），人们常常在其间通行。人们通过一条路径在两地之间通行，其中路径是一系列的街道，从第一个地点到另一个。一种交通工具（车或自行车）可以在一条路径上通行，当且仅当经过的所有街道都至少与它一样宽。每个新修的街道连接关键位置其中之二，有着宽度 $W$。这个宽度可以被任意分割为自行车道和机动车道。在隆德，一些工程师最近发明了宽度为 $0$ 的车和自行车（它们可以在宽度为 $0$ 的道路通行）。 这些工程师测量了城市中车和自行车的宽度。对于每一对关键位置，他们知道其间通行的最宽的车和最宽的自行车的宽度，但政$ $府还要求更宽的车和自行车不能在其间通行。 形式化地，对于任意 $i,j$（$0\le i < j\le N-1$），你都知道两个整数 $C_{i,j}$ 和 $B_{i,j}$。你的任务是构造一个街道网络连接这 $N$ 个位置。街道的宽度均为 $W$，但对于任意街道 $s$，你可以选择它的自行车道宽度 $b_s$ 和机动车道宽度 $W-b_s$。这个网络必须满足以下要求： - 必须可以在任意两个位置间通行。这可能需要一辆宽度为 $0$ 的自行车或车。 - 对于每一对位置 $i,j$（其中 $i < j$），可以只借助宽度至少为 $C_{i,j}$ 的机动车道，在 $i,j$ 间通行。同时，$C_{i,j}$ 是最大的有这一性质的数。这意味着，对于所有 $i,j$ 间的路径，必须满足至少一条街道的机动车道宽度不超过 $C_{i,j}$。 - 对于每一对位置 $i,j$（其中 $i < j$），可以只借助宽度至少为 $B_{i,j}$ 的自行车道，在 $i,j$ 间通行。同时，$B_{i,j}$ 是最大的有这一性质的数。 你能帮隆德政$ $府设计一个这样的街道网络吗？因为预算有限，你可以修建至多 $2023$ 条街道。你可以在同一对关键位置间修建多条街道，但你不能修建一条连接自己和自己的街道。所有街道都是双向的。

第一行两个整数 $N,W$，表示关键位置数量和街道宽度。 接下来 $N-1$ 行包含 $C_{i,j}$。其中的第 $j$ 行包含所有满足 $i < j$ 的 $C_{i,j}$。因此第一行只会包含 $C_{0,1}$，第二行包含 $C_{0,2}$ 和 $C_{1,2}$，第三行包含 $C_{0,3},C_{1,3},C_{2,3}$，以此类推。 接下来 $N-1$ 行包含 $B_{i,j}$，格式同 $C_{i,j}$。

如果不存在符合要求的街道网络，输出 `NO`。 否则，第一行一个整数 $M$，表示你修建的街道数。 接下来 $M$ 行，每行三个整数 $u,v,b$，表示一条自行车道宽度为 $b$（机动车道宽度为 $W-b$）的连接 $u,v$ 的街道。 你可以使用至多 $2023$ 条街道。你输出的街道必须满足 $0\le b\le W$，$0\le u,v\le N-1$ 且 $u\ne v$。你可以在同一对关键位置间使用多条街道（可以有不同的自行车道宽度）。 如果有多解，你可以输出任意一个。

**样例 $1$ 解释** 在样例 $1$ 中，街道的宽度为 $1$，我们需要宽度至少为 $1$ 的自行车道和机动车道各一条连接 $0,1$。解决方案是用两条分开的街道连接，一条自行车道宽度为 $1$，另一条机动车道宽度为 $1$。  --- **样例 $2$ 解释** 在样例 $2$ 中，街道的宽度依然是 $1$，需要有一条宽度为 $1$ 的自行车道连接任意两个关键位置，且有宽度为 $1$ 的机动车道连接 $1,2$ 和 $2,3$。这与 $C_{1,3}=0$ 矛盾，不应该有宽度为 $1$ 的从 $1$ 到 $3$ 的机动车道，而我们可以合并两条先前提到的路径组成这样一条路径。因此不可能构造出一个符合要求的街道网络。 --- **样例 $3$ 解释** 在样例 $3$ 中，下图的街道网络满足所有要求。例如，应该有一条宽度为 $1=C_{0,5}$ 的机动车道在 $0,5$ 之间（路径 $0\to 2\to 4\to 5$），一条宽度为 $3=B_{0,5}$ 的自行车道在 $0,5$ 之间（路径 $0\to 3\to 4\to 5$）。同时，可以验证，不存在路径有着更大的宽度下限。注意样例 $3$ 可能有很多其他解法。  --- **数据范围** 对于全部数据，$2\le N\le 500$，$1\le W\le 10^6$，$0\le C_{i,j},B_{i,j}\le W$。 - 子任务一（$10$ 分）：所有 $C_{i,j}$ 都相同，所有 $B_{i,j}$ 都相同，$N\le 40$。 - 子任务二（$5$ 分）：所有 $C_{i,j}$ 都相同，所有 $B_{i,j}$ 都相同。 - 子任务三（$17$ 分）：$N\le 40$。 - 子任务四（$18$ 分）：$W=1$。 - 子任务五（$19$ 分）：所有 $B_{i,j}$ 都相同。 - 子任务六（$31$ 分）：无特殊限制。