OI

CODEVS 1922 骑士共存问题

题目描述 Description

在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。

对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

输入描述 Input Description

第一行有2 个正整数n 和m (1<=n<=200, 0<=m<n^2)，分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障碍的方格坐标。

输出描述 Output Description

将计算出的共存骑士数输出

样例输入 Sample Input

3 2

1 1

3 3

样例输出 Sample Output

5

Solution

观察到一匹在\((x,y)\)的马跳跃后如果为\((tx,ty)\)，我们有\((x+y)%2\not=(tx+ty)%2\)。

也就是说，我们可以将棋盘看成一个二分图，答案就是这个二分图的“最大独立子集”。

那么二分图的\(X\)集合中是所有\((x,y) (x+y)%2=0\)的边，\(Y\)集合中是所有\((x,y) (x+y)%2=1\)的边，中间根据马跳“日”字连边即可。

对于这个二分图我们假设求出了最大匹配，那么根据定理最大独立子集是节点数减去二分图的最大匹配。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

#include <cstdio>
int n, m;
const int dx[8] = {-2,-1,1,2,2,1,-1,-2};
const int dy[8] = {1,2,2,1,-1,-2,-2,-1};
bool del[210][210];
int id[210][210];
int cnt = 2;
int S, T;
struct edge_type {
	int to, next, f;
} edge[900005];
int cnte = 1, h[50005];
void ins(int u, int v, int w) {
	++cnte;
	edge[cnte].to = v;
	edge[cnte].f = w;
	edge[cnte].next = h[u];
	h[u] = cnte;
	++cnte;
	edge[cnte].to = u;
	edge[cnte].f = 0;
	edge[cnte].next = h[v];
	h[v] = cnte;
}
int q[50005];
int dis[50005];
bool bfs() {
	for (int i = 0; i <= T; ++i) dis[i] = -1;
	int head, tail;
	head = tail = 0;
	q[tail++] = S;
	dis[S] = 0;
	int now;
	while (head<tail) {
		now = q[head++];
		for (int i = h[now]; i; i = edge[i].next) {
			if (dis[edge[i].to] == -1 && edge[i].f) {
				q[tail++] = edge[i].to;
				dis[edge[i].to] = dis[now] + 1;
			}
		}
	}
	return dis[T] != -1;
}
int min(int a, int b) {
	return a < b ? a : b;
}
int cur[50005];
int dfs(int now, int a) {
	if (now == T || a == 0) return a;
	int ret = 0, f;
	for (int &i = cur[now]; i; i = edge[i].next) {
		if (dis[edge[i].to] != dis[now] + 1) continue;
		if (f = dfs(edge[i].to, min(a, edge[i].f)) > 0) {
			a -= f;
			ret += f;
			edge[i].f -= f;
			edge[i^1].f += f;
			if (!a) break;
		}
	}
	if (!ret) dis[now] = -1;
	return ret;
}
int Dinic() {
	int ret = 0;
	while (bfs()) {
		for (int i = 0; i <= T; ++i) cur[i] = h[i];
		ret += dfs(S, 1000000007);
	}
	return ret;
}
int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			del[i][j] = false;
	int x, y;
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &x, &y);
		del[x][y] = true;
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (!del[i][j])
				id[i][j] = cnt++;
	S=1;T=cnt;
	for (int i = 0; i <= T; ++i) h[i] = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j){
			if (del[i][j]) continue;
			if ((i+j)%2==0) {
				ins(S,id[i][j],1);
				for (int k = 0; k < 8; ++k) {
					int tx = i + dx[k], ty = j + dy[k];
					if (1<=tx&&tx<=n&&1<=ty&&ty<=n&&!del[tx][ty])
						ins(id[i][j],id[tx][ty],1000000007);
				}
			}
			else ins(id[i][j],T,1);
		}
	int flow = Dinic();
	printf("%d", n*n-m-flow);
}