P1129

link 题解没一个说为什么能用最小割的...（当然可能是只有我不知道） 设交换后行、列数相同的第 \(x\) 行和第 \(y\) 列（\(x,y\) 为原始位置），发现它们的交点现在位于 \((i,i)\)，原来位于 \((x,y)\)。因为无论怎么交换位置，原来的交点仍是交点。 所以可以得出一个 ......

挺喜欢的一题。 首先我们很容易观察到一个性质：每一行和每一列上的黑色方格的数量是不变的，只能改变它在那一行和那一列的排列顺序。由此若是有某一行或某一列上没有黑色方格，直接输出 No 即可。此时我们考虑的情况就是每一行和每一列上至少都会有一个黑色方格。 这时有一个结论：若有解我们可以仅通过交换行来达成 ......

#include<iostream> #include<algorithm> #include <queue> using namespace std ; const int N=6e4,M=1e5+10; const int inf =1e9+7; int all=1,hd[N],go[M],w[ ......