记录编号	87652	评测结果	AAAATAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	90
用户昵称	Chenyao2333	是否通过	未通过
代码语言	C++	运行时间	1.178 s
提交时间	2014-02-06 18:04:12	内存使用	3.60 MiB

#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

const int MAXN=200+5;
const int MAXP=MAXN*MAXN+10;

int youhua=0;

struct edge{
	int from,to;
};

struct two_sub_graph_matching{
	int n,m;
	vector<int> G[MAXP];
	edge edges[MAXP*8];
	int link[MAXP];
	bool vis[MAXP]; 
	void add_edge(int from,int to){
		edges[m++]=(edge){from,to};
		edges[m++]=(edge){to,from};
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	bool find(int u){
		vis[u]=true;
		for(int i=0;i<G[u].size();i++){
			edge &e=edges[G[u][i]];
			if(vis[e.to])continue;
			if(link[u]==e.to)continue;
			vis[e.to]=true;
			if(!link[e.to] || find(link[e.to])){
				link[u]=e.to;
				link[e.to]=u;
				return true;
			}
		}
		return false;
	}
	
	int maximum_matching(){
		int num=youhua;
		//
		for(int i=0;i<=n;i++){
			if(!link[i]){
				memset(vis,0,sizeof(vis));
				num+=find(i);
			}
		}
		return num;
	}
}solver;

int nn,mm;
bool graph[MAXN][MAXN]={0};

void read(){
	//int m;
	scanf("%d %d",&nn,&mm);
	int x,y;
	for(int i=0;i<mm;i++){
		scanf("%d %d",&x,&y);
		graph[x][y]=true;
	}
}

int op_x[8]={1,1,2,2,-1,-1,-2,-2};
int op_y[8]={2,-2,1,-1,2,-2,1,-1};

inline int code(int x,int y){
	//printf("x:%d y:%d code:%d\n",x,y,(x-1)*nn+y);
	return (x-1)*nn+y;
}

void add_edges(){
	solver.n=nn*nn;solver.m=0;
	memset(solver.link,0,sizeof(solver.link));//
	bool is_red=true;
	for(int i=1;i<=nn;i++){
		is_red=i%2;
		for(int j=1;j<=nn;j++){
			if(is_red || graph[i][j]){is_red=!is_red;continue;}
			for(int k=0;k<8;k++){
				int x=i+op_x[k];int y=j+op_y[k];
				if(!graph[x][y] && x>=1 && x<=nn && y>=1 && y<=nn){
					solver.add_edge(code(i,j),code(x,y));
					
					if(k==5){
						solver.link[code(i,j)]=code(x,y);
						solver.link[code(x,y)]=code(i,j);
						youhua++;
					}
					
				}
			}
			is_red=!is_red;
		}
	}
}

int solve(){
	read();
	add_edges();
	int ans=solver.maximum_matching();
	return nn*nn-mm-ans;
}

void open(){
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
}

int main(){
	open();
	int ans=solve();
	printf("%d",ans); 
	return 0;
}