Description：

给一个 $N\times N$ 的黑白方阵，问是否有方法能通过交换任意行或列使得主对角线上都是黑格子。

$1\le N\le 200$

Solution：

发现交换行或列的操作并不会将在同一行或同一列的黑格子拆开，也并不会将不在同一行或同一列的黑格子合到一起，也就是说要想能让主对角线都是黑格子，在初始情况下就要让不同行有黑格子在不同列，也就是说行和列以黑格子为边有最大匹配，跑匈牙利检查最大匹配是否等于 $N$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases;

int n;

#define MAXN 201

int p[MAXN][MAXN];

struct edge

{

    int to,nxt;

}e[MAXN * MAXN * 2];

int edgenum = 0;

int lin[MAXN * 2] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

void init()

{

    edgenum = 0;

    memset(lin,0,sizeof(lin));

    return;

}

int match[MAXN * 2];

bool v[MAXN * 2];

bool find(int k)

{

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(!v[e[i].to])

        {

            v[e[i].to] = true;

            if(match[e[i].to] == -1 || find(match[e[i].to]))

            {

                match[e[i].to] = k;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    scanf("%d",&testcases);

    for(int cases = 1;cases <= testcases;++cases)

    {

        init();

        scanf("%d",&n);

        for(int i = 1;i <= n;++i)

        {

            for(int j = 1;j <= n;++j)

            {

                scanf("%d",&p[i][j]);

                if(p[i][j] == 1)

                {

                    add(i,j + n);

                }

            }

        }

        memset(match,-1,sizeof(match));

        int ans = 0;

        for(int i = 1;i <= n;++i)

        {

            memset(v,0,sizeof(v));

            if(find(i))++ans;

        }

        if(ans == n)puts("Yes");

        else puts("No");

    }

    return 0;

}