====== 匈牙利算法 ======

===== 二分图 =====

**二分图**（**Bipartite graph**）是一类特殊的**图**，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。

{{https://pic1.zhimg.com/80/v2-81f21981c992bc0b5b1acf04b37ff6c2_720w.jpg| img}}

可以看到，在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的**最大匹配数**和**最小点覆盖数**。

===== 最大匹配问题 =====

{{https://pic3.zhimg.com/80/v2-3d25cee47f59884f46deaea9c7dc95ba_720w.jpg| img}}

最大匹配问题相当于，**假如你是红娘，可以撮合任何一对有暧昧关系的男女，那么你最多能成全多少对情侣**？（数学表述：在二分图中最多能找到多少条没有公共端点的边）

具体实现比较简单，直接看代码：

<code cpp>
int M, N;            //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}
</code>

**时间复杂度：**

邻接矩阵最坏为：$O(n^3)$

邻接表：$O(mn)$

**空间复杂度：**

邻接矩阵：$O(n^2)$

邻接表：$O(n+m)$
===== 最小点覆盖问题 =====

另外一个关于二分图的问题是求**最小点覆盖**：我们想找到**最少**的一些**点**，使二分图所有的边都**至少有一个端点**在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

**（König定理）**

> 一个二分图中的最大匹配数**等于**这个图中的最小点覆盖数。
> 
> [[http://www.matrix67.com/blog/archives/116|证明]]

===== 例题 =====

[[https://www.luogu.com.cn/problem/P1129|P1129 [ZJOI2007]矩阵游戏]]

[[https://vijos.org/p/1204|（vijos1204） CoVH之柯南开锁]]

===== 参考链接 =====

[[https://zhuanlan.zhihu.com/p/96229700|算法学习笔记(5)：匈牙利算法]]