匈牙利算法(什么是匈牙利算法？Hall定理是什么

谈匈牙利算法自然避不开Hall定理，即是对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是对于X的任意一个子集A，和A邻接的点集为T(A)，恒有│T(A)│>=│A│ 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为

1．任给初始匹配M；

2．若X已饱和则结束，否则进行第3步；

3．在X中找到一个非饱和顶点x0，作V1←{x0},V2←Φ； 4．若T(V1)=V2则因为无法匹配而停止，否则任选一点y∈T(V1)V2； 5．若y已饱和则转6，否则做一条从x0→y的可增广道路P，M←M?E(P)，转2；

6．由于y已饱和，所以M中有一条边(y,z)，作V1←V1∪{z},V2←V2∪{y}，转4； 设数组up[1..n]---标记二分图的上半部分的点。 don[1..n]---标记二分图的下半部分的点。 map[1..n，1..n]---表示二分图的上，下部分的点的关系。 True-相连，false---不相连。 over1[1..n]，over2[1..n]标记上下部分的已盖点。 use[1..n，1..n]-表示该条边是否被覆盖。 对读入数据进行处理，对于一条边(x，y)，起点进集合up，终点进集合don。标记map中对应元素为true。 1.寻找up中一个未盖点。 2.从该未盖点出发，搜索一条可行的路线，即由细边出发，由细边结束，且细粗交错的路线。 3.若找到，则修改该路线上的点所对应的over1，over2，use的元素。重复步骤1。 4.统计use中已覆盖的边的条数total，总数n减去total即为问题的解。