P12463 题解

qbf！ · 2025-05-10 15:17:03 · 题解

容易发现问题是一个费用流模型，考虑经典技巧：曼哈顿距离转切比雪夫距离。

此时连边的费用即为 \max(|x-x_1|,|y-y_1|)+\max(|x-x_2|,|y-y_2|) ，拆开绝对值，根据 \max 的分配律我们只需建立 16 个虚点。

进一步，我们注意到 (x,y) 的系数只有 9 种，因此只需 9 个虚点，然后我们只需用堆维护虚点向源点汇点以及虚点之间的边权最大值即可。

这样每次增广只需求一个 k=9 个点的最长路，总时间复杂度为 \mathcal O(k^3n+k^2n\log n)。