题解 【P3355 骑士共存问题】

$\texttt{Description}$

给你一个 $n\times n$ 的棋盘，有 $m$ 个点不能放马，求最多能放多少个马使得这些马互不攻击。马不存在蹩马腿一说。

$\texttt{Data Range:}1\le n\le 200$

$\texttt{Solution}$

第一眼：我会爆搜！！！！11

第二眼：题目都说了是网络流，这题又感觉可以建立二分图模型，如果两个位置不能同时有妈放马就连一条边。问题在于如何对这些点分组使得同一组内的点不会连边。

观察一匹马会跳到哪些位置。

容易发现一只位于 $(x,y)$ 的马可以跳到 $(x+1,y+2),(x+2,y+1),(x-1,y+2),(x+2,y-1)…$ 它们都有一个共同点——横纵坐标之和奇偶性和原来不一样！那么按照 $x+y$ 的奇偶性分组即可。

那么这样分组后按照上文所述方式连边跑跑二分图最大独立集就行了。二分图的最大独立集是点数减去最大匹配边数。如何证明就不展开了。

然而的跑匈牙利是 $O(n^4)$ 的，所以交上去被卡成90了。匈牙利又不像网络流那么假，所以直接回归Dinic正教就行啦~

$\texttt{Code}$

#include <cstdio>
#include <cstring>
#include <queue>

const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
const int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
const int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
struct Edge {
	int to, cap, nxt;
} e[400005];
int head[40005], cur[40005], dis[40005], t, tot = 1;
bool ban[40005];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap) {
	e[++ tot].to = v, e[tot].cap = cap, e[tot].nxt = head[u], head[u] = tot;
	e[++ tot].to = u, e[tot].cap = 0, e[tot].nxt = head[v], head[v] = tot;
}
bool bfs() {
	memset(dis, 0, sizeof dis);
	memcpy(cur, head, sizeof cur);
	Q.push(0);
	dis[0] = 1;
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		for (int i(head[u]); i; i = e[i].nxt)
			if (e[i].cap && !dis[e[i].to])
				dis[e[i].to] = dis[u] + 1, Q.push(e[i].to);
	}
	return dis[t];
}

int dfs(const int u, int low) {
	if (u == t) return low;
	int res(0), flow(0);
	for (int i(cur[u]); i; i = e[i].nxt) {
		cur[u] = i;
		if (low && e[i].cap && dis[u] + 1 == dis[e[i].to])
			if (flow = dfs(e[i].to, min(low, e[i].cap))) {
				res += flow, low -= flow;
				e[i].cap -= flow, e[i ^ 1].cap += flow;
			}
	}
	return res;
}

int Dinic() {
	int Maxflow(0);
	while (bfs()) Maxflow += dfs(0, INF);
	return Maxflow;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	t = n * n + 1;
	for (int i(1); i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		ban[(x - 1) * n + y] = true;
	}
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= n; ++ j)
		if ((i + j & 1) && !ban[(i - 1) * n + j]) {
			int pos((i - 1) * n + j);
			AddEdge(0, pos, 1);
			for (int k(0); k <= 7; ++ k) {
				const int tx(i + dx[k]), ty(j + dy[k]);
				if (tx < 1 || ty < 1 || tx > n || ty > n) continue;
				if (ban[(tx - 1) * n + ty]) continue;
				AddEdge(pos, (tx - 1) * n + ty, 1);
			}
		} else AddEdge((i - 1) * n + j, t, 1);
	printf("%d\n", n * n - m - Dinic());
	return 0;
}