lp1129 ZJOI2007 矩阵游戏

提示：行列匹配。

---

当知道这一题是行列匹配之后，做法就非常显然了。
我们观察发现，如果将每个行与每个列标上序号的话，题目的要求就是求两个排列，使得黑格子排在主对角线上。
然后我们考虑每一个黑格子，我们发现，在最终情况下的每一个黑格子，它所在的行的序号和列的序号均与开始时的序号相同。
故而，所求的两个排列中，相同位置的行和列在开始时的交点必然是黑色的。
所以，每个黑格子就在行列之间连一条边，用行来匹配列，如果都能一一匹配则说明有解。

#include<iostream>
#include<cstdio>
int mp[205][205];
int n,usd[205],vis[205],dep;
inline bool dfs(int X){
	for(int i=1;i<=n;++i){
		if(!mp[X][i]){
			continue;
		}
		if(vis[i]!=dep){
			vis[i]=dep;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	return 0;
} 
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		usd[i]=0,vis[i]=0;
		for(int j=1;j<=n;++j){
			scanf("%d",&mp[i][j]);
		}
	}
	dep=0;
	for(int i=1;i<=n;++i){
		++dep;
		if(!dfs(i)){
			puts("No");
			return;
		}
	}
	puts("Yes");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}