前置知识

本文第一部分（算法介绍部分）与这篇文章完全相同。但「用作示例的题目不同」，本文的题目更贴合实际应用，而这篇文章的题目更加的偏向模板，而且用python写的。

二分图的概念在图论基础之染色法判定二分图。本文主要讲述判定二分图的算法「匈牙利算法」。

「二分图的匹配」：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

「二分图的最大匹配」：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

匈牙利算法

抽象模型

该算法的主要作用就是「求二分图的最大匹配的数量」。

该算法可以用“比喻”来理解。

我们把自己看做“月老”，二分图的一部分是“男同学集合”，另一部分是“女同学集合”。两个集合中的某些同学具有好感，我们的目的是“把具有好感的男女同学匹配为情侣，要求是匹配的情侣数量最多”。

如下图，互相连线表示具有好感，我们要在其中找出可以匹配的最大数量。

算法流程

遍历整个男同学集合，从第一个男同学开始，寻找和他具有好感的女同学，只要找到了就暂时把他俩配成一对。

如果和当前男同学X具有好感的女同学A已经被配对给了别的同学怎么办呢？此时比较常规的做法是继续去和下一个具有好感的女同学配对。

但是，该算法的做法是「找到和这位女同学A匹配的男同学B是哪位，看下这位男同学B是否有其他的女同学C可以配对，如果有就让这位男同学B和其他人C配对」。这样当前男同学X就可以和女同学A进行配对啦。

「示例」

1. 遍历到1号男同学，发现他和2号女同学具有好感，因此，我们先将他俩连一条红绳。

2. 遍历到2号男同学，发现他和1号女同学具有好感，因此，他俩也可以连一条红绳。

3. 遍历到3号男同学，发现他和2号女同学具有好感，2号女同学已经和1号男同学配对了。

   此时关键来了，再看1号男同学发现他还和4号女同学具有好感，那么问题就简单了。我们给1号男和2号女一条绿绳子，让他们分开。

4. 然后再把1号男和4号女配对，3号男和2号女配对，皆大欢喜。

5. 最后把4号男和3号女配对。获得最大匹配数量，4对。

AcWing 372. 棋盘覆盖

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

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

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

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

「输出格式」
输出一个整数，表示结果。

「数据范围」

1≤N≤100,
0≤t≤100

「输入样例」

8 0

「输出样例」

32

题目描述

一个n*n的棋盘，想在上面放长2宽1的骨牌，并且有些格子不可以放，问最多可以放多少块骨牌。

题目分析

乍一看，和二分图好像没有啥关系，但是我们可以调整一下思路，我们发现本题的骨牌所占面积是长度2宽度1，也就是无论竖着放还是横着放都要占用「两个」单位的格子，无形之中似乎和「二分图」产生了玄之又玄的联系。

进一步的，我们「把每个格子都抽象为点」，那么两个格子放置一块骨牌，就可以被看作是「两个相邻点之间连了一条边」，继续按照这个模型思考，我们发现「所有连的边是不能有公共点的」，因为每个格子只能被使用一次，不可能两条边使用了同一个格子。如此，我们发现本题转换成了「最多选取多少条边，可以使选中的边没有公共点」，这就是我们上面「最大匹配」的含义。

那么，如何才能和「二分图」扯上关系呢？

在染色法判定二分图中，我们知道了「二分图一定可以被染成两种颜色，使得每条边的两个点一定是不同颜色的」。

基于上述性质，有一种经典的做法，我们可以把所有的格子分为「奇数格」和「偶数格」，作为二分图的两个集合，分别染不同的颜色，染色之后，我们就可以发现整个图可以被成功染色。

上图中，我们假设整个棋盘根据「奇数格」和「偶数格」被染成「黑蓝」两种颜色，最终结果我们发现「任意 横或者竖 占两个单位面积 的骨牌 均是由 黑蓝两色 组成的」。

因此，整个问题就可以抽象为「以格子作为点，相邻两点之间可以连接一条边，问 最多可以选取多少条边，使选中的边没有公共点，并且整个图符合二分图」。

Code

在实现中，需要考虑一个小问题，如何判断「奇数格」或者「偶数格」呢？

我们可以直接「把每个格子的横坐标和纵坐标加起来的 和」，作为一个点，如果点是奇数，就是奇数格；点是偶数，就是偶数格。

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

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

// 匈牙利算法模板
int find(int x, int y) {
    // 遍历当前点的四个邻点
    for (int i = 0; i < 4; i ++ ) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 or a > n or b < 1 or b > n) continue;
        // 判断点是否合法 以及 是否已经被使用了
        if (g[a][b] or st[a][b]) continue;
        st[a][b] = true; // 标记邻点已经使用
        PII t = match[a][b]; // 邻点的配对情况
        // 未配对 或者 能给邻点的配对 换掉
        if (t.x == 0 or find(t.x, t.y)) { 
            // 就把 当前点 和 邻点 配对
            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 and !g[i][j]) {
                memset(st, 0, sizeof st);
                if (find(i, j)) res ++ ;
            }
        }
    }
    cout << res << endl;
    return 0;
}

「END」