题意
有 \(a+b+1\) 个会动的棋子,在一个大小为 \(n\times m\) 的棋盘上,棋盘上有一些点有障碍。棋子中,有 \(a\) 个红色棋子,\(b\) 个蓝色棋子,和 \(1\) 个既能当作红棋子又能当作蓝棋子的通配棋子。
一个局面是好的,当且仅当对于每个格子,要么这个格子上没有棋子,要么这个格子上恰好存在一个红棋子与一个蓝棋子。
每个棋子有自己的初始位置 \((x_i,y_i)\) 和速度 \(t_i\),其中 \(t_i\) 表示自己走到相邻的格子所需要的时间。
你可以控制所有棋子的移动。请问最少多少时间后能达到处于一个好的局面。或输出无解。
\(1 \le n,m \le 22,0 \le a,b \le n \times m,1 \le t_i \le 10^9\)。
题解
首先 \(|a-b|=1\),否则无解。然后就变成 \(k\) 个红棋子与 \(k\) 个蓝棋子。
乍一看是二分图匹配。但实际上每个格子只能容纳一对棋子,故不能直接套用。
类似二分图,我们不难想到用网络流来解决这种匹配问题。因为每个棋子到任意格子的距离是已知的,故尝试二分答案。
首先将每个格子拆为入点和出点,其间连一条边。依次考虑红棋子 \(i\) 与格子 \(j\),如果 \(i\) 到 \(j\) 的时间不大于当前二分的 \(mid\),则从 \(i\) 连一条边到 \(j\) 的入点。同理,如果蓝棋子 \(i\) 到格子 \(j\) 的时间不大于 \(mid\),则从 \(j\) 的出点连一条边到 \(i\)。再从源点到所有红棋子连边,从所有蓝棋子到汇点连边。所有边的容量均为 \(1\)。跑最大流,判断其是否等于 \(k\) 即可。
这种做法的时间复杂度为 \(O(n^6 \log a)\),其中 \(a\) 为最大时间。显然不能通过。
发现瓶颈在于二分答案。因为网络流有一个很好的性质:往网络中加边,不必重构网络,直接跑就可以得出新的最大流。于是尝试另一种方式:对于所有连接棋子与格子的边,按照其时间从小到大加入。每加一条边跑一次最大流。则当最大流等于 \(k\) 时,加入的边的时间就是答案。复杂度为 \(O(n^4 \times n^4)=O(n^8)\)。
这样就有新的优化空间了。考虑将边分块:设有 \(t\) 条边,每 \(\sqrt t\) 条分为一组。每次加入一组并跑最大流。当最大流等于 \(k\) 时,再将这组的边重新一条条加入。这样的复杂度为 \(O(\sqrt{n^4} \times n^4)=O(n^6)\)。可以通过。
但实际上因为大常数,你还是会 TLE on test 87。解决办法是卡常,或者像我一样:分块套分块。设一个阈值 \(\alpha\),先将块长设为 \(t^{\alpha}\),等最大流等于 \(k\) 时,再将当前块分块,块长为 \(\displaystyle t^{\alpha^2}\)。则复杂度为 \(\displaystyle O((t^{1-\alpha}+t^{\alpha(1-\alpha)}+t^{\alpha^2})\times n^4)\),易知 \(\alpha=\frac{\sqrt5-1}{2}\),化简一下就是 \(n^{5.528}\)。可以通过。
标签:二分,le,格子,题解,times,棋子,alpha,CF513F2 From: https://www.cnblogs.com/FishJokes/p/17027292.html