题目大意

给出一个$n\times n$的矩阵，矩阵节点可以是白色或是黑色

现在有两种操作，一种是交换任意两行，一种是交换任意两列

求是否有可能由原图通过操作得到一个左上角与右下角的连线上的点均为黑色的图

数据范围

$1\leqslant n\leqslant 200$

题解

同行或者同列的点，无论怎么操作仍然同行或者同列

现在问题就是，在原图中能否找到$n$个不同行也不同列的黑色点

行看作$x$集合，列看作$y$集合。第$i$行第$j$列的黑色点，就是$x$集合里的$i$和$y$集合里的$j$连边

由于二分图的性质，我们可以得到二分图最大匹配就是原图中能找到最多的不同行也不同列的黑色点

判断是否完美匹配就得出题目的答案

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x7fffffff
using namespace std;

int map[250][250],vis[250],link[250];
int n,t;

int check(int x){
    For(i,1,n)
        if ((!vis[i])&&(map[x][i])){
            vis[i]=1;
            if ((!link[i])||(check(link[i]))) {link[i]=x;return 1;}
        }
    return 0;
}
int hungry(){
    For(i,1,n){
        memset(vis,0,sizeof(vis));
        if (!check(i)) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(link,0,sizeof(link));memset(map,0,sizeof(map));
        scanf("%d",&n);
        For(i,1,n) For(j,1,n){
            int x;scanf("%d",&x);
            if (x) map[i][j]=1;
        }
        if (hungry()) printf("Yes\n");
        else printf("No\n");
    }
}