自动搬运

查看原文

来自洛谷，原作者为

	Night_Aurora **

搬运于2025-08-24 21:21:18，当前版本为作者最后更新于2017-08-06 15:54:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到下面都有详细的代码也没什么可解释的，说一下推导过程吧

最终状态是（1,1）（2，2）...(n,n)都有一个点

我们把点看成匹配边的话，就是每行和每列都做到了匹配

换言之就是N个行和N个列都有匹配时，一定能转换成最终状态

所以就如S向每行所对应的点连边，每列所对应的点向T连边

每个1的块就是某行和某列的边

再逆过来转换到初始状态，我们发现交换行本质就是交换S向这两行连的边，所以匹配数不变

同理交换列也是

所以只要按照最初状态建二分图跑最大流，就是可能的最终状态的最大流

当且仅当最大流是N的时候可以转换到最终状态