题解 P5222 【Game】

· · 题解

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跑得过。。

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