棋盘覆盖

原题链接

题目描述

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

---

KM算法

考虑一个格子 \((i,j)\):

• \(i+j\) 为偶数:不妨记这样的格子为白格子.
• \(i+j\) 为奇数:不妨记这样的格子为黑格子.

如果这个白格子没有被禁止,那么就让它向周围没有被禁止的黑格子连有向边,表示 如果选择这条边(在这两个格子上放骨牌)会对答案有1的贡献.显然白格子周围都是黑格子,所以白格子之间不会有边.那么这就是一个二分图最大匹配的模型。

代码

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool find(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a && a <= n && b && b <= n && !g[a][b] && !st[a][b]) {
            st[a][b] = true;
            auto t = match[a][b];
            if (t.ff == -1 || find(t.ff, t.ss)) {
                match[a][b] = {x, y};
                return true;
            }
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }

    memset(match, -1, sizeof match);

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if ((i + j) % 2 && !g[i][j]) {
                memset(st, false, sizeof st);
                if (find(i, j)) res++;
            }

    cout << res << endl;

    return 0;
}