题解：P10937 車的放置 | 二分图最大匹配匈牙利算法学习笔记

· · 题解

前置知识：

  1. 什么是二分图？

    若把一个 n 个点的无向图可以分成两个部分（非空且不含重复结点，一般称为左部点和右部点），两个部分内部的点都没有边直接相连，那么这个图就被称为二分图。
    一个图是二分图，当且仅当不存在奇环。

  2. 什么匹配？

    任意两条边都没有公共点的边集称为图的一组匹配。

  3. 什么是最大匹配：

    二分图中包含最多的边的一组匹配称为二分图的最大匹配。

  4. 增广路：

    【《算法竞赛进阶指南（李煜东著）》定义】

    • 假设任意一个匹配 S，则这个匹配中的所有边被称为“匹配边”，而不在这个集合的边称为“非匹配边”，匹配边的端点称为“匹配点”，而其他结点称为“非匹配点”。如果二分图中存在一个路径 path 使得非匹配边与匹配边轮流出现，那么称 path 是匹配 S 的增广路，也叫交错路。

    【OI-wiki 定义】

    • 交错路（alternating path）始于非匹配点且由匹配边与非匹配边交错而成。
    • 增广路（augmenting path）是始于非匹配点且终于非匹配点（除了起始的点）的交错路。增广路中边的数量是奇数。
  5. 增广路的性质：
    1. 长度 len 是奇数。
    2. 路径上第 1,3,5,\dots,len 条边是非匹配边，第 2,4,6,\dots,len-1 条边是匹配边。
  6. 推论：
    1. 增广路上非匹配边比匹配边数量多 1，如果将增广路上的匹配边和未匹配边反转，则匹配数量会增加 1 且依然是交错路。
    2. 二分图的一组匹配 S 是最大匹配，当且仅当图中不存在 S 的增广路。

匈牙利算法（又称增广路算法）：

  1. 主要思路：

    因为增广路长度为奇数，路径起始点非左即右，所以我们先考虑从左边的未匹配点找增广路。注意到因为交错路的关系，增广路上的第奇数条边都是非匹配边，第偶数条边都是匹配边，于是左到右都是非匹配边，右到左都是匹配边。于是我们给二分图定向，问题转换成，有向图中从给定起点找一条简单路径走到某个未匹配点，此问题等价给定起始点 s 能否走到终点 t。那么只要从起始点开始 DFS 遍历直到找到某个未匹配点，\Theta(m)。 未找到增广路时，我们拓展的路也称为交错树。——摘自 OI-wiki

  2. 主要过程：
    1. 设 S=\varnothing，即所有边都是非匹配边。
    2. 寻找任意一条增广路 path，把路径上所有边的匹配状态取反，得到一个更大的匹配 S'。
    3. 重复 2. 的步骤，直到图中不再存在增广路。
  3. 右部点 y 能与左部点 x 匹配的条件：
  4. 正确性：

    当一个点变为匹配点后，只会因为状态取反改变匹配对象，而不可能变回非匹配点。

  5. 时间复杂度：

    因为要枚举 n 个点，总复杂度为 \Theta(nm)。

    对于本题：

  6. 题意简述：
  7. 分析：

    有两个十分显然的结论：

    1. 每行、每列最多只能放一个“車”；
    2. 没个“車”最多只能在一行或一列出现。
  8. 思路：

    可以把 n 行看为左部点，把 m 列作为右部点，那么本题就可以转化为二分图的最大匹配。

  9. 代码： 
    #include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 9;
vector<int> g[maxn];
int n, m, t, ans, match[maxn << 1];
bitset<(maxn << 1)> dat[maxn], vis;
inline bool dfs(const int u)
{
for (int v : g[u])
    if (!vis[v])
    {
        vis[v] = true;
        if (!match[v] || dfs(match[v]))
        {
            match[v] = u;
            return true;
        }
    }
return false;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> t;
for (int i = 1, x, y; i <= t; i++)
    cin >> x >> y, dat[x][y] = true;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (!dat[i][j])
            g[i].push_back(j + n);
for (int i = 1; i <= n; i++)
    vis.reset(), ans += dfs(i);
cout << ans;
}

    二分图的其他重要性质：

    （证明暂时省略，具体参考 OI-wiki）

  10. 二分图的最小点覆盖（König 定理）：

    最小点覆盖定义：选最少的点，满足每条边至少有一个端点被选。
    二分图中，最小点覆盖 = 最大匹配。

  11. 二分图最大独立集

    最大独立集定义：选最多的点，满足两两之间没有边相连。
    因为在最小点覆盖中，任意一条边都被至少选了一个顶点，所以对于其点集的补集，任意一条边都被至多选了一个顶点，所以不存在边连接两个点集中的点，且该点集最大。因此二分图中，最大独立集的大小等于 n 减去最小点覆盖。

    其他与鸣谢：

  12. 其他：

    由于本题解作者是当成学习笔记写的，如果有写错或者哪里看不懂欢迎也希望读者可以在评论区反馈。

  13. 鸣谢：

    感谢《算法竞赛入门经典训练指南（刘汝佳、陈锋著）》帮助本人入门。
    感谢《算法竞赛进阶指南（李煜东著）》，让本人对二分图有了更深刻的理解。
    感谢 OI-wiki 提供本人对二分图更全面的认识。
    感谢 @wangbinfeng 完成本文章。（咋还有鸣谢自己的？）

\color{grey}{\tiny{\texttt{发现上面的签名是动图了吗？}}}