自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 23:02:44，当前版本为作者最后更新于2024-09-16 14:16:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：匈牙利算法（二分图最大匹配），如果不会欢迎阅读我写的另一篇题解。

本题和 P10937 車的放置没有什么本质区别，所以请先阅读我上面给出的题解链接，本题的唯一难点在于建图。

考虑到每行每列最多只能放一个棋子这个条件不再满足，我们就要寻找新的建图方式。

考虑到，“骑士”（“马”）走“日”，那么一定要让所有的日的对角线两端的节点颜色不同，发现每行每列分别为黑白交替恰巧能满足需求（具体见下）。那么建图时判断一下奇偶，求最大独立集即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 9, mx[] = {0, -2, -2, -1, -1, 1, 1, 2, 2}, my[] = {0, -1, 1, -2, 2, -2, 2, -1, 1};
vector<int> g[maxn * maxn];
int n, m, t, ans, vis[maxn * maxn], match[maxn * maxn];
bitset<maxn> dat[maxn];
inline bool dfs(const int u, const int idx)
{
	for (int v : g[u])
		if (vis[v] != idx)
		{
			vis[v] = idx;
			if (!match[v] || dfs(match[v], idx))
			{
				match[v] = u;
				return true;
			}
		}
	return false;
}
signed main()
{
	// freopen("dat.in", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m >> t;
	for (int i = 1, x, y; i <= t; i++)
		cin >> x >> y, dat[x][y] = true;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (!dat[i][j])
			{
				for (int k = 1; k <= 8; k++)
				{
					const int x = i + mx[k], y = j + my[k];
					if (x < 1 || x > n || y < 1 || y > m || dat[x][y])
						continue;
					if ((x + y) % 2)
						g[(i - 1) * m + j].push_back((x - 1) * m + y);
				}
			}
	for (int i = 1; i <= n * m; i++)
		ans += dfs(i, i);//小技巧：这样可以不用每次重置 vis 数组
	cout << n * m - t - ans;
}

本题有超高倍经验（好像五六道吧，具体不附上了），这个代码的时间复杂度较大但一般跑不满，如果某道题 TLE 了可以考虑修改奇偶建图（把代码中的奇数则建图改为偶数则建图），或者将正序枚举改为倒叙枚举均可降低代码实际运行速度。不过这本质上还是面向数据编程，如果可以建议学习正解的网络流（虽然但是网络流好像理论时间复杂度也不太好，不过总是跑不满就是了）。