题解 P1129 【[ZJOI2007]矩阵游戏】

· · 题解

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

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

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

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

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

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

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

同理交换列也是

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

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