[ZJOI2007]矩阵游戏（最大匹配）

题目链接

题解

两眼题

考虑每一行，如果当前列为1，则行与列连边

于是我们左部是每一行，右部是列，可以发现，如果有解，当且仅当每一列都有行与之匹配

跑匈牙利即可

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=40003;
int match[MAXN];
bool vis[MAXN];
int Head[MAXN],to[MAXN<<1],Nt[MAXN<<1],tot;
int t,n;

void add(int x,int y){
    Nt[++tot]=Head[x];
    to[tot]=y;
    Head[x]=tot;
}

bool dfs(int x){
    for(int i=Head[x],y;i;i=Nt[i]){
        if(vis[y=to[i]])continue;
        vis[y]=1;
        if(!match[y]||dfs(match[y])){
            match[y]=x;return true;
        }
    }
    return false;
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        memset(Head,0,sizeof(Head));tot=0;memset(Nt,0,sizeof(Nt));memset(match,0,sizeof(match));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int a;cin>>a;
                if(a==1)add(i,j+n);//个人理解原因，不加n也行
            }
        }
        int i;
        for(i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i));
            else break;
        }
        if(i==n+1)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MAXN=40003;

int match[MAXN];

bool vis[MAXN];

int Head[MAXN],to[MAXN<<1],Nt[MAXN<<1],tot;

int t,n;

void add(int x,int y){

Nt[++tot]=Head[x];

to[tot]=y;

Head[x]=tot;

}

bool dfs(int x){

for(int i=Head[x],y;i;i=Nt[i]){

if(vis[y=to[i]])continue;

vis[y]=1;

if(!match[y]||dfs(match[y])){

match[y]=x;return true;

}

return false;

}

int main(){

cin>>t;

while(t--){

cin>>n;

memset(Head,0,sizeof(Head));tot=0;memset(Nt,0,sizeof(Nt));memset(match,0,sizeof(match));

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

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

int a;cin>>a;

if(a==1)add(i,j+n);//个人理解原因，不加n也行

}

int i;

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

memset(vis,0,sizeof(vis));

if(dfs(i));

else break;

}

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

else printf("No\n");

}

return 0;

}

发送评论编辑评论

题解

代码

发送评论 编辑评论

发送评论编辑评论