P5182 棋盘覆盖题解

· · 题解

前置知识：

为什么一定要这么划分？

因为这样两个相邻的格子一定是不同的颜色，连边时一定都是一黑一白。

不懂的可以自己画一下图。

如果两个相邻的格子都可以放置棋子，就从黑格连向白格。

那么答案就等同于二分图最大匹配的答案，用增广路算法扫一遍黑格就行了。

时间复杂度 O(n^4+t^2)。

AC code

这里我以横坐标加纵坐标的奇偶性判定黑白格。

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int match[N*N];
bool vis[N*N],a[N][N];
int head[N*N],nxt[N*N*2],ver[N*N*2],tot=0;
inline void add(int u,int v){
    nxt[++tot]=head[u];
    ver[tot]=v;
    head[u]=tot;
}
bool dfs(int u){//增广路算法 
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(!vis[v]){
            vis[v]=1;
            if(!match[v] || dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    int n,t,ans=0;
    memset(a,0,sizeof(a));
    cin>>n>>t;
    for(int i=1;i<=t;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=1;
    }
    for(int i=1;i<=n;i++){//横边 
        for(int j=2;j<=n;j++){
            if(!a[i][j] && !a[i][j-1]){
                int x=(i-1)*n+j;
                int y=(i-1)*n+j-1;
                if((i+j)%2) add(x,y);//从黑连向白 
                else add(y,x);
            }
        }
    }
    for(int i=2;i<=n;i++){//竖边 
        for(int j=1;j<=n;j++){
            if(!a[i][j] && !a[i-1][j]){
                int x=(i-1)*n+j;
                int y=(i-2)*n+j;
                if((i+j)%2) add(x,y);//从黑连向白 
                else add(y,x);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i+j)%2){//只扫黑格 
                memset(vis,0,sizeof(vis));
                if(!a[i][j] && dfs((i-1)*n+j)) ans++;
            }
        }
    }
    cout<<ans;
}