记录编号	269806	评测结果	AATAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	90
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	未通过
代码语言	C++	运行时间	1.464 s
提交时间	2016-06-14 06:34:40	内存使用	2.50 MiB

#include<stdio.h>
#include<string.h>
#define pos(i,j) (i*n-(n-j))
const int maxn=80010;
struct Node{
	int to,next;
}e[maxn<<1];
int n,m,len,head[maxn],cy[maxn],vis[maxn],Time;
bool f[maxn];
void Insert(int x,int y){len++;	e[len].to=y; e[len].next=head[x]; head[x]=len;}
bool Path(int x){
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(vis[y]^Time){
			vis[y]=Time;
			if(!cy[y]||Path(cy[y])){
				cy[y]=x;
				return true;
			}
		}
	}
	return false;
}
int main(){
	freopen("knight.in","r",stdin);freopen("knight.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		f[pos(x,y)]=1;
	}
	int c1[8]={1,1,2,2,-1,-1,-2,-2},c2[8]={2,-2,1,-1,2,-2,1,-1};
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		int x=pos(i,j);
		if(!f[x]&&(i+j)&1){
			for(int k=0;k<8;k++){
				int xx=i+c1[k],yy=j+c2[k];
				if(xx>n||yy>n||xx<1||yy<1)continue;
				int y=pos(xx,yy);
				if(!f[y])Insert(x,y);
			}
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		int x=pos(i,j);
		if((i+j)&1&&!f[x]){
			Time++;
			tot+=Path(x);
		}
	}
	//printf("%d\n",tot);
	printf("%d\n",n*n-m-tot);
	return 0;
}