#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105,
dx[] = {-1,+1, 0, 0},
dy[] = { 0, 0,-1,+1};
struct Edge{
int to,next;
}edge[N*N*4];
int n,m,en,oddn,even,head[N*N],match[N*N],number[N][N];
bool ishole[N][N],used[N*N];
void add(int x,int y){
edge[en].to = y;
edge[en].next = head[x];
head[x] = en++;
}
void init(){
scanf("%d%d",&n,&m);
for (int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
ishole[x][y] = true;
}
oddn = even = 0;
for (int x=1;x<=n;x++)
for (int y=1;y<=n;y++)
if (!ishole[x][y]){
if ((x+y)%2) number[x][y] = ++oddn;
else number[x][y] = ++even;
}
memset(head,-1,sizeof(head));
en = 0;
int x0,y0;
for (int x=1;x<=n;x++)
for (int y=1;y<=n;y++)
if ((x+y)%2){
for (int i=0;i<4;i++){
x0 = x+dx[i];
y0 = y+dy[i];
if (x0<1 || x0>n || y0<1 || y0>n || ishole[x0][y0]) continue;
add(number[x][y],number[x0][y0]);
}
}
}
bool can(int u){
for (int v,p=head[u];~p;p=edge[p].next){
v = edge[p].to ;
if (!used[v]){
used[v] = true;
if (!match[v] || can(match[v])){
match[v] = u;
return true;
}
}
}
return false;
}
void hungary(){
int ans(0);
memset(match,0,sizeof(match));
for (int i=1;i<=oddn;i++){
memset(used,0,sizeof(used));
if (can(i)) ans++;
}
printf("%d\n",ans);
}
int main(){
freopen("qipan.in","r",stdin);
freopen("qipan.out","w",stdout);
init();
hungary();
return 0;
}
posted on 2011-10-27 21:59
龙在江湖 阅读(204)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
竞赛题解_TYVJ