BZOj1059: [ZJOI2007]矩阵游戏

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1059

Solution

显然原来同行/同列的两个位置，无论如何变化始终是同行/同列。
所以只要统计出不同行也不同列的黑格个数
相当于每行要匹配各自不同的列，将它转化成二分图，若(i,j)为黑，则i行向j列连边。
最后做一遍最大匹配，判断匹配数是否达到n。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 40005
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
struct edge{
    ll to,next;
}e[N*2];
ll head[N],flag[N],link[N];
ll T,n,x,b,tot;
void add(ll u,ll v){
    e[++tot]=(edge){v,head[u]}; head[u]=tot;
}
ll dfs(ll u){
    for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
        if (!flag[v]){
            flag[v]=1;
            if (!link[v]||dfs(link[v])){
                link[v]=u; return 1;
            }
        }
    return 0;
}
int main(){
    T=read();
    while (T--){
        memset(e,0,sizeof e);
        memset(link,0,sizeof link);
        memset(head,0,sizeof head);
        n=read(); tot=b=0;
        for (ll i=1;i<=n;i++)
        for (ll j=1;j<=n;j++){
            x=read();
            if (x) add(i,j);
        }
        for (ll i=1;i<=n;i++){
            memset(flag,0,sizeof flag);
            if (!dfs(i)) b=1;
        }
        if (b) puts("No"); else puts("Yes");
    }
}