记录编号	149060	评测结果	EEEAEAEEEE
题目名称	[网络流24题] 骑士共存	最终得分	20
用户昵称	new ioer	是否通过	未通过
代码语言	C++	运行时间	0.698 s
提交时间	2015-02-18 10:30:54	内存使用	8.89 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
bool map[201][201];
char ch[500000],*ptr=ch;
const int inf=0x3f3f3f3f;
int n,m,en,ans,len=1,d[40001],g[40001],p[400001],q[400001],pos[201][201];
struct edge{int to,next,cap;}e[400000];
const int dx[]={-2,-2,-1,-1,1,1,2,2},dy[]={1,-1,2,-2,2,-2,1,-1};
void in(int &x){
	x=0;while(*ptr<48) ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;
}
void add(int x,int y,int z){
	e[++len].to=y,e[len].next=g[x],e[len].cap=z,g[x]=len;
	e[++len].to=x,e[len].next=g[y],e[len].cap=0,g[y]=len;
}
bool bfs(){
	int l=1,r=1;
    memset(d,0,sizeof d);
    q[1]=0,d[0]=1;
    while(l<=r){
        int x=q[l++];
        for(int to,i=g[x];i;i=e[i].next)
            if(!d[to=e[i].to]&&e[i].cap)
            	d[to]=d[x]+1,q[++r]=to;
    }
    return d[en];
}
int dfs(int x,int y){
    if(x==en||!y) return y;
    int flow=0,to,f;
    for(int &i=p[x];i;i=e[i].next){
        if(d[to=e[i].to]==d[x]+1&&e[i].cap){
            f=dfs(to,std::min(y,e[i].cap));
            flow+=f,y-=f;
            e[i].cap-=f,e[i^1].cap+=f;
            if(!y) break;
        }
    }
    return flow;
}
int main(){
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
	fread(ptr,1,500000,stdin);
	in(n),in(m),en=n*n+1,ans=n*n-m;
	for(int x,y;m;m--) in(x),in(y),map[x][y]=1;
	for(int k=0,i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			pos[i][j]=++k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(map[i][j]) continue;
			if(i+j&1){add(pos[i][j],en,1);continue;}
			add(0,pos[i][j],1);
			for(int u=0;u<8;u++){
				int x=i+dx[u],y=j+dy[u];
				if(x<=0||y<=0||x>n||y>n||map[x][y]) continue;
				add(pos[i][j],pos[x][y],1);
			}
		}
	while(bfs()){
		memcpy(p,g,sizeof p);
		ans-=dfs(0,inf);
	}
	printf("%d",ans);
}