「CH6901」骑士放置

「CH6901」骑士放置

传送门

将棋盘黑白染色，发现“日”字的两个顶点刚好一黑一白，构成一张二分图。

那么我们将黑点向源点连边，白点向汇点连边，不能同时选的一对黑、白点连边。

当然，障碍点不会被连任何边。

那么我们每割掉一条黑白点之间的边，就会减少 \(1\) 的答案。

那么为了答案最大就是 $n \times m - t - $ 最小割。

参考代码：

#include <cstring>

#include <cstdio>

#include <queue>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 1e4 + 5, __ = 1e5 + 5, INF = 2147483647;

const int dx[] = { -1, -1, -2, -2, 1, 1, 2, 2 };

const int dy[] = { -2, 2, -1, 1, -2, 2, -1, 1 };

int tot = 1, head[_], nxt[__ << 1], ver[__ << 1], cap[__ << 1];

inline void Add_edge(int u, int v, int d)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, cap[tot] = d; }

inline void link(int u, int v, int d) { Add_edge(u, v, d), Add_edge(v, u, 0); }

int N, M, T, ch[102][102], s, t, dep[_], cur[_];

inline int id(int x, int y) { return y + (x - 1) * M; }

inline int bfs() {

	static queue < int > Q;

	while (!Q.empty()) Q.pop();

	memset(dep, 0, sizeof dep);

	Q.push(s), dep[s] = 1;

	while (!Q.empty()) {

		int u = Q.front(); Q.pop();

		for (rg int i = head[u]; i; i = nxt[i]) {

			int v = ver[i];

			if (dep[v] == 0 && cap[i] > 0)

				dep[v] = dep[u] + 1, Q.push(v);

		}

	}

	return dep[t] > 0;

}

inline int dfs(int u, int flow) {

	if (u == t) return flow;

	for (rg int &i = cur[u]; i; i = nxt[i]) {

		int v = ver[i];

		if (dep[v] == dep[u] + 1&& cap[i] > 0) {

			int res = dfs(v, min(cap[i], flow));

			if (res) { cap[i] -= res, cap[i ^ 1] += res; return res; }

		}

	}

	return 0;

}

inline int Dinic() {

	int res = 0;

	while (bfs()) {

		for (rg int i = s; i <= t; ++i) cur[i] = head[i];

		while (int d = dfs(s, INF)) res += d;

	}

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	read(N), read(M), read(T);

	for (rg int x, y, i = 1; i <= T; ++i) read(x), read(y), ch[x][y] = 1;

	s = 0, t = N * M + 1;

	for (rg int i = 1; i <= N; ++i)

		for (rg int j = 1; j <= M; ++j) {

			if (ch[i][j]) continue;

			if (i + j & 1) {

				link(s, id(i, j), 1);

				for (rg int k = 0; k < 8; ++k) {

					int ni = i + dx[k], nj = j + dy[k];

					if (ni >= 1 && ni <= N && nj >= 1 && nj <= M && !ch[i][j])

						link(id(i, j), id(ni, nj), 1);

				}

			} else link(id(i, j), t, 1);

		}

	printf("%d\n", N * M - T - Dinic());

	return 0;

}