题解：P14581 [LNCPC 2025] 海鸥奇遇

· · 题解

这是本题的官方题解。

首先，因为海鸥数量等于食物数量，等于要求的指挥步数，一步指挥最多让一只海鸥飞离，所以海鸥与食物一一对应，每步指挥都要让一只海鸥飞离。

因此，原问题可以建模为二分图完美匹配问题。建立二分图：如果一只海鸥与一个方向距离最近的一份食物之间没有空格子，那么对它俩连一条无向边。因为一只海鸥最多与它的上下左右四个方向的各一份食物各连一条边，所以这张二分图的大小为 O(n)。然后使用匈牙利算法（O(n^2)）或者网络流（O(n^{\frac{3}{2}})）求最大匹配。如果最大匹配数等于 n，那么得到了初步的完美匹配；否则，报告无解。

然后，指挥海鸥需要有顺序。建立有向图：如果一只海鸥与它当前匹配的食物之间有若干只海鸥，那么指挥这只海鸥的时间都要比这些海鸥的早，从这只海鸥向这些海鸥各连一条有向边。因为指挥一只海鸥的时间最多要求比它的上下左右四个方向的各一只海鸥的晚，所以一只海鸥的入度最多为四，这张有向图的大小为 O(n)。

现在需要解决当前这张有向图有环的问题。之所以从海鸥 A 向海鸥 B 连一条有向边，是因为海鸥 A 与它匹配的食物 C 之间有海鸥 B，所以海鸥 B 也有条件匹配食物 C。因此，对于当前这张有向图上的一个简单环 s_0→\cdots→s_{i-1}→s_i\cdots→s_{k-1}→s_0，设海鸥 s_i 匹配的食物为 f_i，则调整为 f_{(i-1+k)\bmod k}。容易证明，调整后的匹配不仅仍然是合法的完美匹配，而且对应的有向图的边数一定会减少。因此，一轮调整操作包含 DFS 找简单环（O(n)）、调整匹配（O(n)）和建立新的有向图（O(n)），只需执行 O(n) 轮调整操作即可让得到的完美匹配对应的有向图无环，这部分总的时间复杂度为 O(n^2)。

最后，对这张有向无环图执行拓扑排序（O(n)），指挥海鸥的顺序即为拓扑序，得到一种合法的指挥方案。

总的时空复杂度：O(n^2)。

Bonus

请思考：在二分图匹配中，如果让食物去匹配海鸥，并且优先匹配距离最近的海鸥，并且求最大匹配使用匈牙利算法，那么由此直接得到的有向图是否一定无环，无需任何调整操作？