记录编号	205908	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.086 s
提交时间	2015-11-05 20:12:15	内存使用	3.18 MiB

#define MAXN 210UL

#include <cstdio>
#include <cstring>

struct Edge{
	int v,nx;
};

Edge edge[MAXN*MAXN<<3];
int n,m,ec,cnt,lim,headlist[MAXN*MAXN],Ans,link[MAXN*MAXN],up[MAXN*MAXN],np;
bool M[MAXN][MAXN];
int opx[8]={1,1,2,2,-1,-1,-2,-2};
int opy[8]={-2,2,-1,1,2,-2,-1,1};

inline int Cal(int x,int y){
	return (x-1)*n+y;
}

inline void Add_Edge(int u,int v){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

bool dfs(int p){
	for(int i=headlist[p];i;i=edge[i].nx){
		if(up[edge[i].v]==np) continue;
		up[edge[i].v]=np;
		if(!link[edge[i].v]||dfs(link[edge[i].v])){
			link[edge[i].v]=p;
			return true;
		}
	}
	return false;
}

inline void Add(int i,int j){
	int x,y,id=Cal(i,j),id2;
	for(int k=0;k<8;k++){
		x=opx[k]+i,y=opy[k]+j,id2=Cal(x,y);
		if(x<1||x>n) continue;
		if(y<1||y>n) continue;
		if(M[x][y]) continue;
		Add_Edge(id,id2);
		Add_Edge(id2,id);
	}
	return;
}

inline void BuildGraph(){
	for(int i=1;i<=n;i++) for(int j=(i&1)+1;j<=n;j+=2) if(!M[i][j])
		Add(i,j);
	return;
}

inline void Work(){
	int id=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
		++id;
		if(M[i][j]) continue;
		if(i+j&1) continue;
		np++;
		if(dfs(id)) Ans++;
	}
	return;
}

int main(){
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
	scanf("%d%d",&n,&m);lim=n*n;
	for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),M[x][y]=true;
	BuildGraph();Work();
	printf("%d",n*n-m-Ans);
	return 0;
}