题解：P5182 棋盘覆盖

· · 题解

题目传送门

机房老师给的二分图练习题，做完回来发现只有一篇题解。那还不得来一发。

由于我们已经知道是二分图。不妨想一下怎么把这题和二分图联系一下。

观察一下发现这个棋盘格点向四周格点建图直接就满足二分图的性质了，就像国际棋盘一样，黑格和白格分别为二分图的左部和右部，那么将骨牌看作边，又由于一格中不能放两个骨牌，即同一个点不能与两条边相连，又要求骨牌最大放置数，这显然又要求二分图最大匹配了。

所以将每个格子看作一个点，每个点向它上方、下方、左边、右边的点建边（如果有的话）。最后跑一边匈牙利算法就行了。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 10010;
int match[maxn], vis[maxn], ans, n, t;
bool in[110][110];
vector <int> v[maxn];
bool solve(int x) {
    if (vis[x]) return 0;
    vis[x] = 1;
    for (int i = 0; i < v[x].size(); i++)
        if (!match[v[x][i]] || solve(match[v[x][i]])) {
            match[v[x][i]] = x;
            return 1;
        }
    return 0;
}//匈牙利算法
int change(int x, int y) {
    return (x - 1) * 100 + y;
}//将点(x, y)压缩成一个数 
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= t; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        in[x][y] = 1;   
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (in[i][j]) continue;
            if (!in[i + 1][j] && i != n) {
                v[change(i, j)].push_back(change(i + 1, j));
                v[change(i + 1, j)].push_back(change(i, j));
            }//连竖直边 
            if (!in[i][j + 1] && j != n) {
                v[change(i, j)].push_back(change(i, j + 1));
                v[change(i, j + 1)].push_back(change(i, j));
            }//连水平边 
        }
    }
    for (int i = 1; i <= n * 100; i ++) {
        memset(vis, 0, sizeof vis);
        if (solve(i)) ans ++;
    }//这里实际上将左部和右部的所有点全跑了一遍，等于答案翻了两倍 
    printf("%d", ans / 2);
}