蓝书二分图例题

CH6801 棋盘覆盖

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=210;

int head[N],nxt[N*2],to[N*2],a[M][M],vis[N],match[N];
int num,m,n,ans;

void add(int x,int y)
{
    nxt[++num]=head[x],to[num]=y,head[x]=num;
}

bool dfs(int x)
{
    for(int i=head[x],y; i ;i=nxt[i])
        if(!vis[y=to[i]])
        {
            vis[y]=1;//一开始写在里面，错了; 
            if(!match[y] || dfs(match[y]))
            {
                match[x]=y; match[y]=x;// 一开始没写第二句，错了； 
                return true ;
            }
        }
    return false ;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==1) continue ;
            int x=i*n+j-n;
            
            if(j<n && !a[i][j+1]) add(x,x+1);
            if(j>1 && !a[i][j-1]) add(x,x-1);
            
            if(i<n && !a[i+1][j]) add(x,x+n);
            if(i>1 && !a[i-1][j]) add(x,x-n);
        }
    
    for(int i=1;i<=n*n;i++)
        if(!match[i])
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans++;
        }
        
    cout<<ans<<endl; 
    return 0;   
}

蓝书二分图例题

原文：https://www.cnblogs.com/lzqlalala/p/11224936.html