2171 棋盘覆盖

/*其实如果把国际棋盘白色的看成集合A，黑的看成集合B。//每个合法的格子与相邻的合法格子有无向边（合法就是没有被删除），//这种最大匹配就是所谓的最大覆盖数。*/#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};const int N=1e4+10;const int V=110;int n,m,num,ans,tot,mp[V][V],id[V][V],match[N],yy[N],head[N],next[N<<2],list[N<<2]; void add(int x,int y){    list[++tot]=y;    next[tot]=head[x];    head[x]=tot;}bool inside(int x,int y){    return x>0&&x<=n&&y>0&&y<=n;}bool hungary(int x){    for(int i=head[x];i;i=next[i]){        if(!yy[list[i]]){            yy[list[i]]=1;            if(!match[list[i]]||hungary(match[list[i]])){                match[list[i]]=x;                return 1;            }        }    }    return 0;}void mapping(){    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            id[i][j]=++num;        }    }    for(int i=1;i<=n;i++){        for(int j=1+!(i&1);j<=n;j+=2){            if(mp[i][j]) continue;            for(int k=0;k<4;k++){                int nx=i+dx[k],ny=j+dy[k];                if(inside(nx,ny)&&!mp[nx][ny]){                    add(id[i][j],id[nx][ny]);                }             }        }    }}void solve(){    for(int i=1;i<=n;i++){        for(int j=1+!(i&1);j<=n;j+=2){            if(mp[i][j]) continue;             memset(yy,0,sizeof yy);            if(hungary(id[i][j])) ans++;         }    }    printf("%d",ans);}int main(){    scanf("%d%d",&n,&m);    for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),mp[x][y]=1;    mapping();    solve();    return 0;}

/*思路：我们可以对棋盘进行染，黑白相间，即相临两格不同色，这样染完色，我们就可以将同种颜色的格子作为一个集合，另外一种颜色作为一个集合，然后相邻格子间存在边的关系   （当然得排除挖去的部分）。求二分图最大匹配*/#include<cstdio>#include<iostream>using namespace std;const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};const int N=210;const int M=N*N;const int inf=0x3f3f3f3f;int n,m,S,T,num,id[N][N],mp[N][N],head[M],dis[M],q[M*5];struct node{    int v,next,cap;}e[M*10];int tot=1;void add(int x,int y,int z){    e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;}bool bfs(){    for(int i=S;i<=T;i++) dis[i]=inf;    int h=0,t=1;    q[t]=S;dis[S]=0;    while(h!=t){        int x=q[++h];        for(int i=head[x];i;i=e[i].next){            int v=e[i].v;            if(e[i].cap&&dis[v]>dis[x]+1){                dis[v]=dis[x]+1;                if(v==T) return 1;                q[++t]=v;            }        }    }    return dis[T]<inf;}int dfs(int x,int f){    if(x==T) return f;    int used=0,t;    for(int i=head[x];i;i=e[i].next){        int v=e[i].v;        if(e[i].cap&&dis[v]==dis[x]+1){            t=dfs(v,min(f,e[i].cap));            e[i].cap-=t;e[i^1].cap+=t;            f-=t;used+=t;            if(!f) return used;        }    }    dis[x]=0;    return used;}int dinic(){    int res=0;    while(bfs()) res+=dfs(S,inf);    return res;}void mapping(){    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            id[i][j]=++num;        }    }    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            if(mp[i][j]) continue;            if((i+j)&1^1){                add(S,id[i][j],1);                for(int k=0;k<4;k++){                    int nx=i+dx[k],ny=j+dy[k];                    if(nx<1||nx>n||ny<1||ny>n||mp[nx][ny]) continue;                    add(id[i][j],id[nx][ny],1);                }            }            else{                add(id[i][j],T,1);            }        }    }}int main(){    scanf("%d%d",&n,&m);S=0;T=n*n+1;    for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),mp[x][y]=1;    mapping();    printf("%d",dinic());    return 0;}