Warning: session_start(): open(/tmp/sess_b835a26a1ac17a2acb21ce70c1e286bf, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 匈牙利算法 ======
===== 二分图 =====
**二分图**（**Bipartite graph**）是一类特殊的**图**，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。
{{https://pic1.zhimg.com/80/v2-81f21981c992bc0b5b1acf04b37ff6c2_720w.jpg| img}}
可以看到，在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的**最大匹配数**和**最小点覆盖数**。
===== 最大匹配问题 =====
{{https://pic3.zhimg.com/80/v2-3d25cee47f59884f46deaea9c7dc95ba_720w.jpg| img}}
最大匹配问题相当于，**假如你是红娘，可以撮合任何一对有暧昧关系的男女，那么你最多能成全多少对情侣**？（数学表述：在二分图中最多能找到多少条没有公共端点的边）
具体实现比较简单，直接看代码：
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;
}
**时间复杂度：**
邻接矩阵最坏为：$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)：匈牙利算法]]