BZOJ 1059: [ZJOI2007]矩阵游戏

传送门

解题思路

二分图匹配，出现1后让这一行和这一列连边，然后跑一遍匈牙利，判断最后的ans是否等于n。刚开始想复杂了，这样连了后还拆点反着连。。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
const int MAXN = 605;
const int MAXM = MAXN*MAXN;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int T,n,a[MAXN][MAXN],ans;
int match[MAXM<<1];
int head[MAXM<<1],cnt,k;
int to[MAXM<<1],nxt[MAXM<<1];
int vis[MAXM<<1],num;

inline void add(int bg,int ed){
    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}

inline bool dfs(int x){
    for(register int i=head[x];i;i=nxt[i]){
        int u=to[i];
        if(vis[u]==num) continue;
        vis[u]=num;
        if(!match[u] || dfs(match[u])) {
            match[u]=x;
            return true;
        }
    }
    return false;
}

int main(){
    T=rd();
    while(T--){
        memset(head,0,sizeof(head));
        memset(match,0,sizeof(match));
        n=rd();ans=0;
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=n;j++){ 
                scanf("%d",&a[i][j]);
                if(a[i][j]==1) k++,add(i,j);
            } 
        for(register int i=1;i<=k;i++){
            num++;
            if(dfs(i)) ans++;
        }
        if(ans==n) puts("Yes");
        else puts("No");
    }
    return 0;
}