题目大意：给定一个 N*N 的矩阵，有些格子是 1，其他格子是 0。现在允许交换若干次行和若干次列，求是否可能使得矩阵的主对角线上所有的数字都是1。

题解：首先发现，交换行和交换列之间是相互独立的。主对角线上是 1 意味着每行都对应着相应的列。现在考虑 1 是行和列之间的边，若对于这张二分图存在一个完美匹配，根据交换列时与行无关，这样总可以使得主对角线全是 1。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=210;

int m[maxn][maxn];

int n,match[maxn];

bool vis[maxn];

void read_and_parse(){

	scanf("%d",&n);

	memset(match,0,sizeof(match));

	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&m[i][j]);

}

bool dfs(int u){

	for(int i=1;i<=n;i++){

		if(!m[u][i]||vis[i])continue;

		vis[i]=1;

		if(!match[i]||dfs(match[i])){

			match[i]=u;return 1;

		}

	}

	return 0;

}

void solve(){

	int ans=0;

	for(int i=1;i<=n;i++){

		memset(vis,0,sizeof(vis));

		if(dfs(i))++ans;

	}

	puts(ans==n?"Yes":"No");

}

int main(){

	int T;scanf("%d",&T);

	while(T--){

		read_and_parse();

		solve();

	}

	return 0;

}