[TYVJ1035] 棋盘覆盖|匈牙利算法|二分图匹配

P1035 棋盘覆盖

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

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

输入格式

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

输出格式

一个数，即最大覆盖格数

测试样例1

输入

8 0

输出

32

备注

经典问题

 

先进行二分图染色，然后匈牙利（0ms）或者网络流（60ms）

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 10005
using namespace std;
int a[105][105];
int yy[N],lk[N],head[N];
int n,m,cnt,ans;
int next[N<<2],list[N<<2];
int dis[N],q[N];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
inline int read()
{
    int a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}
inline int c(int x,int y) {return (x-1)*n+y;}
inline void insert(int x,int y)
{
    next[++cnt]=head[x];
    head[x]=cnt;
    list[cnt]=y;
}
bool Hungary(int v)
{
    for (int i=head[v];i;i=next[i])
        if (!yy[list[i]])
        {
            yy[list[i]]=1;
            if (!lk[list[i]]||Hungary(lk[list[i]]))
            {
                lk[list[i]]=v;
                return 1;
            }
        }
    return 0;
}
int main()
{
    n=read(); m=read();
    int x,y;
    memset(a,1,sizeof(a));
    for (int i=1;i<=m;i++) x=read(),y=read(),a[x][y]=0;
    for (int i=1;i<=n;i++)
        for (int j=1+(i%2==0);j<=n;j+=2)
            if (a[i][j])
                for (int k=0;k<4;k++)
                {
                    x=i+dx[k]; y=j+dy[k];
                    if (x<1||x>n||y<1||y>n||!a[x][y]) continue;
                    insert(c(i,j),c(x,y));
                }
    for (int i=1;i<=n;i++)
        for (int j=1+(i%2==0);j<=n;j+=2)
            if (a[i][j])
            {
                memset(yy,0,sizeof(yy));
                if (Hungary(c(i,j))) ans++;
            }
    printf("%d",ans);
    return 0;
}