https://www.luogu.com.cn/problem/P1129
n*n个格子的矩阵有黑白两色，问是否能经过有限次行交换和列交换使得主多角线上都是黑色（用1表示）。
主对角线上全是黑色，我们可以反着推，对于一个单位矩阵，任意次行交换列交换之后矩阵总是满足一个一个性质，每一行只与唯一的列交点为1，就是不存在任意两个点1的行数相等，也不存在列数相等。行交换列交换都是可逆的，所以如果矩阵满足这样的性质就一定可以交换得到主对角线都是1，找这样的性质首先想到了八皇后，用dfs去遍历，可是n的范围是200啊一定会超时的。最后看了题解，只能拍手称妙啊，佩服的五体投地。不是每一行都要存在有一个唯一的列为1，那不就相当于可以想象在行和列之间建条边，行和列分别是二分图两部分中的点，如果存在最大匹配等n就是可以满足那个性质，或者说是每个行都可以找到一个列与他匹配。接下来就是套板子了
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=210;
int n,m,a[N][N];
bool st[N];
int p[N],h[N],e[N*N],ne[N*N],idx;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool find(int x)
{
for(int i=h[x];i!=-1;i=ne[i])
{
int y=e[i];
if(!st[y])
{
st[y]=1;
if(!p[y]||find(p[y]))
{
p[y]=x;//保存每一列是否匹配过以及和谁匹配
return 1;
}
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
memset(h,-1,sizeof h);
cin>>n;
idx=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j])
add(i,j);//只需要一条i到j的边就可以了
}
bool flag=1;
memset(p,0,sizeof p);
for(int i=1;i<=n;i++)
{
memset(st,0,sizeof st);//清空标记，给i匹配过程中都找过那些点
if(!find(i))
{
flag=0;
break;
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}