匈牙利算法是什么？

匈牙利算法自然避免不了霍尔定理，即对于二部图G，存在一个匹配的m，X的所有顶点相对于m饱和的充要条件是:对于X的任意子集A，与A相邻的点集是T(A)，总有:│T(A)│>；= │A│

匈牙利算法基于霍尔定理中充分性证明的思想，其基本步骤如下:

1.任何初始匹配m；

2.如果X饱和，结束，否则进行步骤3；

3.在X中求一个不饱和顶点x0为v1 ← {x0}，v2←φ；

4.如果T(V1) = V2，会因为无法匹配而停止，否则选择一点y∈T(v 1)\ V2；

5.如果y饱和，转到6；否则，从x0 →y做一条增广路p，M←M？E(P)，转2；

6.因为Y饱和，所以M中有一条边(Y，z)，是v 1←v 1 ∨{ z }，v2←v2 ∨{ Y }，转4；

让阵列向上[1...n]-标记二分图上部的点。

向下[1...n]-标记二分图下部的点。

地图[1..n，1..n]-表示二分图的上半部分和下半部分中的点之间的关系。

真-连接，假-不连接。

超过1 [1...n]和大于2 [1...n]标记上部和下部的覆盖点。

使用[1..n，1..n]-指示边缘是否被覆盖。

首先，对读入的数据进行处理。对于边(x，y)，起点进入设置，终点进入设置。将地图中相应的元素标记为true。

1.在up中找到一个未覆盖的点。

2.从未覆盖的点出发，搜索可行路线，即以细边为起点，以细边为终点，粗细交错的路线。

3.如果找到，修改over1，over2的元素并使用对应于路线上的点。重复步骤1。

4.统计使用中的覆盖边总数，总数n减去总数就是问题的解。