记录编号	93285	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.189 s
提交时间	2014-03-25 15:33:27	内存使用	3.23 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int V(40011), E(320011), dx[8] = {-2, -1, 1, 2, -2, -1, 1, 2}, dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int h[V], n[E], e[E], et, v[V], tv, m[V], nn;
bool b[V];
inline int f(int x, int y){
	return x + (y - 1) * nn;
}
inline void ins(int f, int t){
	n[++et] = h[f]; h[f] = et; e[et] = t;
	n[++et] = h[t]; h[t] = et; e[et] = f;
}
bool dfs(int p){
	for (int i = h[p]; i; i = n[i])
		if (v[e[i]] != tv){
			v[e[i]] = tv;
			if (!m[e[i]] || dfs(m[e[i]])) return m[e[i]] = p;
		}
	return false;
}
int main(){
	freopen("knight.in", "r", stdin);
	freopen("knight.out", "w", stdout);
	int mm, i, j, k, t, l, ans;
	scanf("%d%d", &nn, &mm);
	for (ans = nn * nn - mm; mm; --mm){
		scanf("%d%d", &i, &j);
		b[f(i, j)] = true;
	}
	for (i = 1; i <=nn; ++i)
		for (j = (i & 1) + 1; j <= nn; j += 2)
			if (!b[t = f(i, j)]) for (k = 0; k < 8; ++k)
				if (i + dx[k] > 0 && i + dx[k] <= nn && j + dy[k] > 0 && j + dy[k] <= nn && !b[l = f(i + dx[k], j + dy[k])]) ins(t, l);
	for (i = 1; i <= nn; ++i)
		for (j = 1; j <= nn; ++j)
			if (i + j & 1 && !b[k = f(i, j)]){
				++tv;
				ans -= dfs(k);
			}
	printf("%d\n", ans);
	return 0;
}