问题分析

核心矛盾与关键观察

题目要求为 YT 市交叉路口分配海拔（西北角固定为 0，东南角固定为 1），使得所有道路上的人流量乘以爬坡体力消耗的总和最小。核心在于明确“海拔分配”与“体力消耗”的数学关联，并将其转化为可计算的模型。

关键观察有两点：

1. 体力消耗的本质：对于连接两点 $u$（海拔 $h_u$）和 $v$（海拔 $h_v$）的道路，若方向为 $u \to v$，则消耗为 $\max(0, h_v - h_u) \times 流量_{u \to v}$。总消耗可拆分为所有道路的单向消耗之和。
2. 海拔的最优分布特性：由于西北角海拔 0 与东南角海拔 1 固定，且体力消耗仅与相对高低有关，最优海拔分配必然是 0-1 分布——即所有交叉路口的海拔要么为 0，要么为 1。若存在海拔为 $0 < h < 1$ 的路口，将其调整为 0 或 1 可进一步降低总消耗（例如，若路口周围“爬坡需求”更多指向它，则设为 0 更优；反之设为 1 更优）。

该观察将问题简化为：将 $(n+1) \times (n+1)$ 个交叉路口分为两组 $S$（海拔 0）和 $T$（海拔 1），满足西北角在 $S$、东南角在 $T$，计算此时的总消耗并求最小值。

0-1 分布下的消耗计算

当海拔仅为 0 或 1 时，体力消耗可进一步简化：

• 对于道路 $u \to v$，若 $u \in S$ 且 $v \in T$（从低海拔到高海拔），则消耗为 $流量_{u \to v} \times 1$（因 $h_v - h_u = 1$）；
• 若 $u \in T$ 且 $v \in S$（从高到低），则消耗为 0（因 $h_v - h_u = -1$，$\max(0, -1) = 0$）；
• 若 $u$ 和 $v$ 同属一组，则消耗为 0（海拔差为 0）。

此时总消耗等价于所有从 $S$ 流向 $T$ 的单向道路的流量之和，问题转化为：寻找 $S$ 和 $T$ 的划分（满足西北角在 $S$、东南角在 $T$），使得跨组单向流量和最小——这正是经典的最小割问题。

模型构建：平面图与对偶图

直接对交叉路口构建网络流模型会面临节点数 $(n+1)^2$ 过大的问题（$n=500$ 时节点数超 25 万，边数更庞大），因此需要利用“城市道路为平面图”的特性，通过对偶图将问题转化为规模更小的单源最短路径问题。

1. 原问题的平面图表示

将 YT 市的道路网络视为平面图：

• 交叉路口为平面图的“顶点”；
• 道路为平面图的“边”；
• 城市被道路划分的 $n \times n$ 个区域为平面图的“面”。

2. 对偶图的构建与意义

平面图的对偶图定义为：

• 对偶图的每个“顶点”对应原平面图的一个“面”；
• 对偶图的每条“边”对应原平面图的一条“边”，且若原边连接两个面，则对偶边连接这两个面对应的对偶顶点。

对于本题，构建对偶图后有两个关键结论：

1. 原问题中 $S$ 和 $T$ 的划分（最小割），对应对偶图中“从原平面图外边界的两个相邻面”到“另两个相邻面”的路径——本质是对偶图的单源最短路径。
2. 原平面图中“从 $S$ 到 $T$ 的边”的流量，对应对偶图中“对应边”的权重。因此，原问题的最小割等价于对偶图中指定两点间的最短路长度。

3. 权重与路径设定

• 对偶图的边权：对于原平面图的每条单向道路 $u \to v$，其对应对偶边的权重设为该道路的流量（因原边的流量是最小割的代价）。
• 起点与终点：根据原问题中西北角（$S$）和东南角（$T$）的位置，对偶图的起点设为“原平面图左上角外侧的面”，终点设为“原平面图右下角外侧的面”——两点间的最短路长度即为原问题的最小总消耗。

算法流程与复杂度

1. 输入解析与流量整合：读取 $4n(n+1)$ 条单向道路的流量，按原平面图的边对应关系整理。
2. 对偶图构建：将原平面图的 $n \times n$ 个区域映射为对偶图的 $(n+1) \times (n+1)$ 个顶点（简化编号为从 $(0,0)$ 到 $(n,n)$），并根据原道路的流量设定对偶边的权重。
3. 最短路求解：由于对偶图的边权均为非负整数（流量为非负），采用 Dijkstra 算法 求解起点到终点的最短路。考虑到 $n=500$ 时对偶图顶点数为 $(501)^2 = 251001$，边数约为 $4 \times 500 \times 501 = 1002000$，使用优先队列优化的 Dijkstra 算法可在 $O(M \log N)$ 时间内完成（$M$ 为边数，$N$ 为顶点数），满足时间限制。
4. 结果输出：将最短路长度四舍五入为整数（实际计算中因流量为整数，结果通常为整数，四舍五入仅为符合题目要求）。

核心思想总结

本题的精髓在于问题转化：

1. 将“连续海拔分配”转化为“0-1 离散分配”，简化消耗计算；
2. 将“0-1 分配的最小消耗”转化为“原平面图的最小割”；
3. 利用“平面图对偶性”将“最小割”转化为“对偶图的最短路”，规避了直接网络流的规模瓶颈。

这种“几何问题→图论模型→算法转化”的思路，是解决复杂规划类问题的典型方法。

算法标签

• 最小割（Min-Cut）
• 网络流（最大流-最小割定理）
• 平面图转对偶图