挺喜欢的一题。
首先我们很容易观察到一个性质：每一行和每一列上的黑色方格的数量是不变的，只能改变它在那一行和那一列的排列顺序。由此若是有某一行或某一列上没有黑色方格，直接输出 No 即可。此时我们考虑的情况就是每一行和每一列上至少都会有一个黑色方格。
这时有一个结论：若有解我们可以仅通过交换行来达成有解的情况。考虑反证：若必须通过至少一次交换列来达成有解，则说明无论我们如何交换行，都会出现至少有一列无法对应其行的情况。并且呢，我们容易知道，交换行列的顺序无关紧要，若先交换第 \(i, j\) 行和再交换第 \(x, y\) 列，等价于先交换第 \(x, y\) 列和再交换第 \(i, j\) 行（随便分讨一下就能证明）。所以我们就可以将所有交换列的操作留到最后进行。设最后一步交换第 \(i\) 列和第 \(j\) 列，那么交换前 \((i, j)\) 和 \((j, i)\) 上一定是黑色方格，且对角线上必定只有 \((i, i)\) 和 \((j, j)\) 是白色方格。这时我们会发现：为什么我们不能通过交换第 \(i\) 行和第 \(j\) 行来达成有解呢？因此矛盾。
我们对于每个黑色方格 \((i, j)\) ，从 \(i\) 向 \(j\) 连一条边，之后对于每个交换行的操作，我们会发现就是把左部点交换了一下节点编号而已，最大匹配并没有改变，因此，若我们交换节点编号后使得第 \(i\) 行都有且只对应第 \(i\) 列，这时最大匹配就是 \(n\) ，我们完全就可以直接就在原图上跑匈牙利就好啦！若原图匹配出 \(n\) 说明就是 Yes ！
#include<bits/stdc++.h>
using namespace std;
#define N 210
int n, tag;
int a[N][N];
int e[N][N], use[N], path[N];
int dfs(int u){
for(int i = 1; i <= n; i ++){
if(e[u][i] && use[i] != tag){
use[i] = tag;
if(path[i] == -1 || dfs(path[i])){
path[i] = u;
return 1;
}
}
}
return 0;
}
signed main(){
// freopen("shuju.in", "r",stdin);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int TN;
cin >> TN;
while(TN--){
memset(e, 0, sizeof e);
memset(use, -1, sizeof use);
memset(path, -1, sizeof path);
cin >> n;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
cin >> a[i][j];
if(a[i][j] == 1) e[i][j] = 1;
}
}
int sum = 0;
for(int i = 1; i <= n; i ++){
tag++;
if(dfs(i)) sum++;
}
if(sum == n) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}