自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:08:24，当前版本为作者最后更新于2019-02-14 21:40:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Game

Upd：之前题目有一点问题，感谢巨佬 @ywwywwyww 指出。题面已经更正，原代码只需改动10字节左右即可AC。

事实上。。出题人也不知道能有什么部分分。。题面上那么多不同的数据范围只是想看看一道网络流能乱搞出什么算法。。

大概50分的朴素建图

可以考虑建一个网格图，对于每一个向上/下的边建一条费用$1$，流量$1$的边，每一条向左/右边建一条费用$0$，流量$Inf$的边，然后最左边连源点，右边连汇点，然后跑费用流，最多扩展$N$次，然后复杂度上界就是$O(N^3M^2)$，发现不够优秀。

这里的上下边的费用就限制了一操作的次数，左右边流量限制了两个棋子不能走到一起。

即使这种玄学图能充分发挥$Spfa$玄学性质，但是可能不能过$M=10^4$的数据,一定不能过$M=10^6$的数据。

70分做法

事实上发现$M$非常大的时候中间有很多空行没有什么卵用，这时候可以删去这些行，然后只留下有障碍的行及其前一行，这样的话就可以优化到$O(N^3T^2)$，但是这个玩意是上界，但是$Spfa$在这种边权只有$0/1/-1$的网格图+随机数据下跑得远不到上界，所以是可以过的。

Upd: 时限改成1s辣！！

所以上述方法就只能拿暴力分了。。那么怎么优化呢？？

100分做法

实际上我们在$0/1/-1$网格图中跑$Spfa$有一个非常简单的优化：用双端队列替换掉原来的队列，然后每一次插入的时候和队头比较，如果更小就插入到队头，否则插入到队尾。这样的话我们跑一次$Spfa$的复杂度就变成了$O(N^2T)$了(-1的边对这种方法有影响，但是最多影响一行内的点)。发现现在的复杂度上界是$O(N^3T)$，$10^8$左右，开O2跑得过。。

代码太丑了，还是不放了吧。。