bzoj 1059 [ZJOI2007]矩阵游戏——匈牙利算法

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1059

发现不管怎么换，同一列的元素还是在同一列，同一行的元素还是在同一行。

所以必要条件是每一行、每一列都至少有一个黑格子。

但这不是充要条件。比如一个L形的就不能。

如果从答案向别的情况变换的话，变换到的各种情况一定是：如果每一列都只贡献一个黑格子，它们能占满所有行。

行列连边跑一个最大匹配看能不能都匹配上就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int T,n,hd[N],xnt,pre[N];

bool flag,vis[N];

struct Ed{

    int nxt,to;Ed(int n=,int t=):nxt(n),to(t) {}

}ed[N*N];

int rdn()

{

    int ret=;char ch=getchar();

    while(ch>''||ch<'')ch=getchar();

    while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();

    return ret;

}

void add(int x,int y)

{

    ed[++xnt]=Ed(hd[x],y);hd[x]=xnt;

}

bool dfs(int cr)

{

    for(int i=hd[cr],v;i;i=ed[i].nxt)

        if(!vis[v=ed[i].to])

        {

            vis[v]=;

            if(!pre[v]||dfs(pre[v]))

            {

                pre[v]=cr;return true;

            }

        }

    return false;

}

int main()

{

    T=rdn();

    while(T--)

    {

        memset(hd,,sizeof hd);xnt=;

        memset(pre,,sizeof pre);flag=;

        n=rdn();int x;

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

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

            {

                scanf("%d",&x);

                if(x)add(i,j);

            }

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

        {

            memset(vis,,sizeof vis);

            if(!dfs(i)){flag=;break;}

        }

        puts(flag?"No":"Yes");

    }

    return ;

}