AcWing 372. 棋盘覆盖

题目传送门

一、二分图应用【匈牙利算法求最大匹配】

前置知识

• 匹配：二分图中两个点集中各取一点进行连边。

• 最大匹配：二分图中左右两边匹配后边的最大数量。

• 匹配点：属于其中一个匹配边的其中一个端点。

• 增广路径：左边点集中的一个非匹配点，沿着非匹配边走到右边点集中的一个匹配点，再沿着匹配边走到左边点集中的一个匹配点，再沿着非匹配边走到右边点集中的一个匹配点 …… 最终走到右边点集中的一个非匹配点。
  

增广路径的起点和终点一定都是非匹配点，增广路径意味着我们可以将所有蓝色（匹配边）和绿色边（非匹配边）互换，这样匹配边的数量就加 \(1\)。

结论
一个最大匹配 ? 不存在增广路径

替无可替，现在最大！

二、题目重述

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

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

题目分析
将格子视为点，所有相邻格子连一条边，然后问题即转化为最多选多少条匹配边，其中所有选出的边没有公共点。即求一个最大匹配。

一个 \(n×m\) 的矩形一定是可以二染色的。

如上图，可以将白色格子和黑色格子分别放在一边，相邻格子之间连一条边，可见边只会存在两个集合之间而不会出现在任一集合内部，故这是一个二分图，因此本题可以用二分图最大匹配做。

如何判断一个点是白色还是黑色？

可以找到一个规律，黑色格子点的横纵下标之和为偶数，白色格子点的横纵下标之和为奇数，称黑色格子为偶点，白色格子为奇点。在做最大匹配时，只需要枚举其中一个点集即可。

三、实现代码

#include 
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 110;

int n; // n*n的矩阵
int t; // t为禁止放置的格子的数量
// 判断一个格子是否是坏点
bool g[N][N], st[N][N];
PII match[N][N];
int dx[] = {-1, 0, 1, 0}; //上右下左
int dy[] = {0, 1, 0, -1}; //上右下左

//匈牙利算法求二分图最大匹配 奇数点白，偶数点黑
bool find(int x, int y) {
    for (int i = 0; i < 4; i++) { //这里就看出使用邻接矩阵的优势了，要不怎么上下左右？
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || tx > n || ty < 1 || ty > n) continue;
        if (st[tx][ty] || g[tx][ty]) continue;

        st[tx][ty] = true;
        PII t = match[tx][ty]; //白点一伙，黑点一伙，求白向黑的最大匹配边数量
        if (t.x == 0 || find(t.x, t.y)) {
            match[tx][ty] = {x, y};
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> t;
    // t为禁止放置的格子的数量
    for (int i = 0; i < t; i++) {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }

    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, 0, sizeof st);
                if (find(i, j)) res++;
            }
    //输出最大匹配
    cout << res << endl;
    return 0;
}