CodeDevil

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1059

【题意】

给定一个n*n的黑白棋盘，可以任意交换矩阵的任两行或任两列，问给定的矩阵能否通过若干次这两种操作，最终主对角线上全是黑色。

【题解】

如果矩阵内(i,j)格为黑色，就由i向j连一条边，判断这个二分图是否有匹配：有则有解，无则无解。

【代码】   (匈牙利都能写错。。。QAQ)

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

bool G[210][210];

int n,lnk[210];

bool vis[210];

 

bool find(int u)

{

    int i;

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

    {

        if (G[u][i] && !vis[i])

        {

            vis[i]=true;

            if (lnk[i]==0 || find(lnk[i]))

            {

                lnk[i]=u;

                return true;

            }

        }

    }

    return false;

}

 

int main()

{

    int T,i,j,c;

    scanf("%d",&T);

    while (T--)

    {

        scanf("%d",&n);

        memset(G,false,sizeof(G));

        memset(lnk,0,sizeof(lnk));

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

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

            {

                scanf("%d",&c);

                if (c) G[i][j]=true;

            }

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

        {

            memset(vis,false,sizeof(vis));

            if (!find(i)) break;

        }

        if (i==n+1) printf("Yes"); else printf("No");

        if (T) printf("\n");

    }

    return 0;

}