棋盘覆盖

二分图最大匹配 372. 棋盘覆盖 - AcWing题库 给定一个 $N$ 行 $N$ 列的棋盘，已知某些格子禁止放置。

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

输入格式

第一行包含两个整数 $N$ 和 $t$，其中 $t$ 为禁止放置的格子的数量。

接下来 $t$ 行每行包含两个整数 $x$ 和 $y$，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

输出格式

输出一个整数，表示结果。

数据范围

$1\le N\le 100$,
$0\le t\le 100$

输入样例：

8 0

输出样例：

32

思路

给一个 $N\times N$ 的棋盘, 用两格的骨牌填满, 并且有些格子无法放置, 求能填多少个。

乍一看和状压DP的题目很像, 不过求的是可行解, 那可以用搜索, 但格子一共$100\times 100$ 也就是 $1e4$, 爆搜复杂度得是 $2^{10000}$ , 肯定超时。

每个骨牌只占两格, 且只有这一种骨牌, 若把每个格子看做一个点, 相邻的格子连一条边, 那么就是求这种匹配对最多有几个, 即最大匹配问题, 而且是两个点匹配, 那么就是二分图。

最大匹配问题可以用匈牙利算法来实现：

1. 定义 $match$ 数组表示每个点对应匹配的另一个点
2. 对于点 $A$ , 枚举它能匹配到的所有点 $B$
   1. 若 $B$ 未被匹配, 或者可以通过 $find(match[B])$ 操作使得原本匹配 $B$ 的点换一个点匹配, 则将 $match[B]=A$

而该题的点是以坐标形式表示, 那么 $match$ 数组也需要开成二维且类型为 pair。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e2 + 10;
typedef pair<int,int> PII;
int g[N][N];
PII match[N][N];
int st[N][N];
int n,m;
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
 
bool find(int x, int y)
{
 
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 1 || a > n || b < 1 || b > n) continue;
        if(st[a][b] || g[a][b]) continue;
        st[a][b] = true;
        
        PII t = match[a][b];
        if(t.first == 0 || find(t.first, t.second))
        {
            match[a][b] = {x,y};
            return true;
        }
    }
    return false;
}
 
 
int main()
{
    cin >> n >> m;
    while(m--)
    {
        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;
}