自动搬运

查看原文

来自洛谷，原作者为

	qbf！ Never Give Up

搬运于2025-08-24 23:15:44，当前版本为作者最后更新于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)$。