如果要保证有解
那么,必定存在从每一行选择一个棋子,能够包括每一列。

#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX 205
struct Line{
int v,next;
}e[10MAXMAX];
int h[MAX],cnt=1;
int vis[MAX],dep;
int match[MAX],N,sum=0,a;
int n;
inline void add(int u,int v){
e[cnt]=(Line){v,h[u]};
h[u]=cnt++;
}
bool dfs(int x){
for (int i=h[x];i;i=e[i].next){
int v=e[i].v;
if (vis[v]!=dep)
{
vis[v]=dep;
if (!match[v]||dfs(match[v]))
{
match[v]=x;
return true;
}
}
}
return false;
}
int main(){
int t;
scanf("%d",&t);
while (t–){
scanf("%d",&n);
int sum=0;cnt=1;
for (int i=1;i<=n;i++)
match[i]=vis[i]=h[i]=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
scanf("%d",&a);
if(a)
add(i,j);
}
}
for (dep=1;dep<=n;dep++)
if (dfs(dep)) sum++;
if (sum==n)
cout<<“Yes”<<endl;
else
cout<<“No”<<endl;
}
}