题目链接
看到题目肯定首先会想到搜索。
然鹅数据范围\(n<=200\)这么大（其实也不算太大），肯定是不行的。
如果\((i,j)\)是\(1\)，从\(i\)向\(j\)连一条边，表示第\(j\)列可以交换第\(i\)列得到，然后跑一遍匈牙利就行了（Dinic我不会啊）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define Close fclose(stdin);fclose(stdout);
using namespace std;
int s; char ch;
inline int read(){
s = 0; ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
return s;
}
const int MAXN = 1010;
const int MAXM = MAXN * MAXN;
int match[MAXN], vis[MAXN];
int n, T, a, Time, head[MAXN], num, ans;
struct Edge{
int next, to;
}e[MAXM << 1];
inline void Add(int from, int to){
e[++num].to = to; e[num].next = head[from]; head[from] = num;
}
int find(int u){
for(int i = head[u]; i; i = e[i].next)
if(vis[e[i].to] != Time){
vis[e[i].to] = Time;
if(!match[e[i].to] || find(match[e[i].to])){
match[e[i].to] = u;
return 1;
}
}
return 0;
}
int main(){
T = read();
while(T--){
memset(head, 0, sizeof head);
memset(match, 0, sizeof match);
num = 0; n = read(); ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(read())
Add(i, j);
for(int i = 1; i <= n; ++i)
++Time, ans += find(i);
if(ans == n) printf("Yes\n");
else printf("No\n");
}
return 0;
}