记录编号	372162	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	ztzshiwo	是否通过	通过
代码语言	C++	运行时间	0.438 s
提交时间	2017-02-17 20:10:33	内存使用	10.55 MiB

#include<ctime>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long LL;
#define getchar getchar_unlocked
#define mem(a,b) memset(a,b,sizeof a)
template<typename T>inline T chkmax(T a,T b){return a>b?a:b;}
template<typename T>inline T chkmin(T a,T b){return a<b?a:b;}
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define rFor(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
const int N=40010;
const int M=800010;
const int inf=0x3f3f3f3f;
using namespace std;
template<typename T>inline void read(T&x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x=f?-x:x;
}
int n,m,maxflow;
int bgn[N],cur[N],nxt[M],to[M],f[M],E;
int pre[N],dep[N],gap[N],q[N];
inline void init(){E=1;}
inline void add_edge(int u,int v,int ew)
{
	nxt[++E]=bgn[u],bgn[u]=E,to[E]=v,f[E]=ew;
	nxt[++E]=bgn[v],bgn[v]=E,to[E]=u,f[E]=0;
}
inline void bfs(int t)
{
	int head=0,tail=0;
	q[++tail]=t;
	while(head<tail)
	{
		int u=q[++head];++gap[dep[u]];
		for(int v,i=bgn[u];i;i=nxt[i])
		{
			if((v=to[i])==t)continue;
			if(!dep[v])dep[q[++tail]=v]=dep[u]+1;
		}
	}
}
inline void get_maxflow(int s,int t,int n)
{
	int u=s;
	bfs(t);For(i,1,n)cur[i]=bgn[i];
	while(dep[s]<n)
	{
		if(u==t)
		{
			++maxflow;
			for(int x=s;x^t;x=to[cur[x]])
				--f[cur[x]],++f[cur[x]^1];
			u=s;
		}
		int i;
		for(i=cur[u];i;i=nxt[i])
			if(dep[to[i]]==dep[u]-1&&f[i]>0)break;
		if(!i)
		{
			if(!(--gap[dep[u]]))break;
			dep[u]=n,cur[u]=bgn[u];
			for(i=bgn[u];i;i=nxt[i])
				if(f[i])dep[u]=chkmin(dep[u],dep[to[i]]+1);
			++gap[dep[u]];
			if(u^s)u=pre[u];
		}
		else cur[pre[to[i]]=u]=i,u=to[i];
	}
}
int cnt,dir[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int mp[210][210],ans;
int main()
{
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
	init();
	int x,y,s,t;
	read(n),read(m);
	while(m--)read(x),read(y),mp[x][y]=-1;
	For(i,1,n)For(j,1,n)if(mp[i][j]^-1)mp[i][j]=++cnt;
	s=cnt+1,t=cnt+2;
	For(i,1,n)
		For(j,1,n)
			if(mp[i][j]^-1)
			{
				if(i+j&1)
				{
					add_edge(s,mp[i][j],1);
					For(k,0,7)
					{
						x=i+dir[k][0],y=j+dir[k][1];
						if(x<1||x>n||y<1||y>n||mp[x][y]==-1)continue;
						add_edge(mp[i][j],mp[x][y],1);
					}
				}
				else add_edge(mp[i][j],t,1);
			}
	get_maxflow(s,t,t);
	printf("%d\n",cnt-maxflow);
	return 0;
}