记录编号	237743	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.726 s
提交时间	2016-03-18 10:24:17	内存使用	8.29 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 40010;
const int inf = 1e7;
bool cant_r[205][205];
int s, t, n, m;
struct node {
	int x, y, num;
}han[9];
class solve_flow {
private:
	struct edge {
		int to, ne, le;
		edge() {}
		edge(int to_, int ne_, int le_) { to = to_, ne = ne_, le = le_;}
	}e[maxn<<4];
	int head[maxn], tot;
	int de[maxn];
	int cur[maxn];
	int q[maxn], be, en;
public:
	inline void add_edge(int fr, int to, int cap) {
		e[++tot] = edge(to, head[fr], cap); head[fr] = tot;
		e[++tot] = edge(fr, head[to], 0); head[to] = tot;
	}
	inline bool bfs() {
		memset(de, 0 ,(t+1)<<2);
		memcpy(cur, head, (t+1)<<2);
		be = en = 1;
		de[s] = 1;
		q[en++] = s;
		int now;
		while(be < en) {
			int now = q[be++];
			for(int i = head[now]; i; i = e[i].ne) {
				int to = e[i].to;
				if(de[to] || e[i].le <= 0) continue;
				de[to] = de[now]+1;
				if(to == t) return true;
				q[en++] = to;
			}
		}
		return de[t];
	} 
	inline int dfs(int now, int min_flow) {
		if(now == t) return min_flow;
		for(int &i = cur[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(de[to] != de[now]+1 || e[i].le <= 0) continue;
			int now_flow = dfs(to, min(e[i].le, min_flow));
			if(!now_flow) continue;
			e[i].le -= now_flow;
			if(i & 1) e[i+1].le += now_flow;
			else e[i-1].le += now_flow;
			return now_flow;
		}
		return 0;
	}
	inline int dinic() {
		int ans = 0, tmp;
		while(bfs()) {
			while(tmp = dfs(s, inf)) ans += tmp;
		}
		return ans;
	}
}smax;
inline void read() {
	scanf("%d %d", &n ,&m);
	s = n*n+1;
	t = s+1;
	int x, y;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		cant_r[x][y] = true;
	}
}
inline void get_han() {
	han[1].x = 2, han[1].y = 1, han[1].num = 2*n+1; 
	han[2].x = 2, han[2].y = -1, han[2].num = 2*n-1;
	han[3].x = 1, han[3].y = 2, han[3].num = n+2;
	han[4].x = 1, han[4].y = -2, han[4].num = n-2;
	han[5].x = -2, han[5].y = 1, han[5].num = 1-2*n;
	han[6].x = -2, han[6].y = -1, han[6].num = -1-2*n;
	han[7].x = -1, han[7].y = 2, han[7].num = 2-n;
	han[8].x = -1, han[8].y = -2, han[8].num = -2-n;
}
inline void solve() {
	get_han();
	int pos, x, y;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(cant_r[i][j]) continue;
			pos = (i-1)*n+j;
			if((j+i) & 1) {
				smax.add_edge(s, pos, 1);
				for(int k = 1; k <= 8; k++) {
					x = i+han[k].x, y = j+han[k].y;
					if(x >= 1 && x <= n && y >= 1 && y <= n && !cant_r[x][y]) {
						smax.add_edge(pos, pos+han[k].num, 1);
					}
				}
			} else {
				smax.add_edge(pos, t, 1);
			}
		}
	}
	printf("%d\n",n*n-m-smax.dinic());
}
int main() {
	freopen("knight.in", "r", stdin);
	freopen("knight.out", "w", stdout);
	read();
	solve();
	return 0;
}