【ZJOI2007】矩阵游戏

题面

https://www.luogu.org/problem/P1129

题解

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#define ri register int
#define N 205
using namespace std;

inline int read() {
  int f=0,ret=0; char ch=getchar();
  while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
  while (ch>='0'&& ch<='9') ret=ret*10+(ch-'0'),ch=getchar();
  return f?-ret:ret;
}
int T,n;
vector<int> to[N];
int match[N],vis[N],tin;

bool dfs(int x) {
  for (ri i=0;i<to[x].size();i++) {
    int y=to[x][i];
    if (vis[y]==tin) continue;
    vis[y]=tin;
    if (!match[y] || dfs(match[y])) {
      match[y]=x;
      return 1;
    }
  }
  return 0;
}

void work() {
  n=read();
  for (ri i=1;i<=n;i++) to[i].clear();
  memset(match,0,sizeof(match));
  memset(vis,0,sizeof(vis));
  for (ri i=1;i<=n;i++)
    for (ri j=1;j<=n;j++) {
      int w=read();
      if (w) to[i].push_back(j);
    }
  tin=0;
  for (ri i=1;i<=n;i++) {
    ++tin;
    if (!dfs(i)) {
      puts("No");
      return;
    }
  }
  puts("Yes");
  return;
}

int main() {
  T=read();
  while (T--) work();
  return 0;
}