题解：P10939 骑士放置

wangbinfeng · 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 了可以考虑修改奇偶建图（把代码中的奇数则建图改为偶数则建图），或者将正序枚举改为倒叙枚举均可降低代码实际运行速度。不过这本质上还是面向数据编程，如果可以建议学习正解的网络流（虽然但是网络流好像理论时间复杂度也不太好，不过总是跑不满就是了）。