本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-25 16:41:23

简单描述一下匈牙利算法：

首先设 $m_u$ 表示每个点的匹配。

尝试对每个点 $u$ 进行匹配，对每一个 $(u, v) \in E$：

• 如果 $v$ 未匹配就直接匹配；

• 否则，尝试重新匹配 $m_v$；如果成功，那么 $(u, v)$ 相配；否则失配，继续找下一个 $v$。

注意到这个过程就是找增广路的过程。第一种情况中的增广路是 $u \to v$；第二种情况中，若设 $m_v$ 的新匹配是 $m_v'$，那么增广路是 $u \to v \to m_v \to m_v'$。

不难注意到，两种情况都使整体匹配数加一，故一个最大匹配中一定是没有增广路的。

再证充分性。

充分性太难了不好证 但是分讨可以证