2171 棋盘覆盖

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 黄金 Gold

题目描述 Description

给出一张n*n(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。

输入描述 Input Description

第一行为n，m（表示有m个删除的格子）
第二行到m+1行为x,y，分别表示删除格子所在的位置
x为第x行
y为第y列

输出描述 Output Description

一个数，即最大覆盖格数

样例输入 Sample Input

8 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

经典问题

分类标签 Tags 点此展开

暂无标签

匈牙利

/*其实如果把国际棋盘白色的看成集合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;
}