匈牙利算法

匈牙利算法(Edmonds算法)步聚：

(1)首先用（*）标记X中所有的非M顶点，然后交替进行步骤（2），（3）。

(2)选取一个刚标记（用（*）或在步骤（3）中用（yi）标记）过的X中顶点，例如顶点x

i，如果

xi与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过,则用（xi）

去标记Y中顶点y。重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。 (3)选取一个刚标记（在步骤(2)中用(xi)标记）过的Y中结点，例如yi，如果yi与x为

同一匹配边的两端点，且在本步骤中x尚未被标记过，则用(yi)去标记X中结点x。重复步骤(3)，直至对刚标记过的Y中结点全部完成一遍上述过程。

(2),(3)交替执行，直到下述情况之一出现为止：

(I)标记到一个Y中顶点y，它不是M顶点。这时从y出发循标记回溯，直到（*）标

记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。

(II)步骤(2)或(3)找不到可标记结点，而又不是情况(I)。

(4)当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非

匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有标记。

(5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止

(算法找不到交替链).

以上算法说穿了，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

下面给出此算法的一个例子：

（1） 置M = 空，对x1-x6标记（*）。

（2）找到交替链（x1, y1）（由标记（x1），（*）回溯得），置M = {(x1, y1)}。

(3)找到交替链（x2, y2）（由标记（x2），（*）回溯得），置M = {(x1, y1), (x2, y2),}。

（4）找到交替链（x3, y1, x1, y4）（如图9.4所示。图中虚线表示非匹配边，细实线表示交替链中非匹配边，粗实线表示匹配边），因而得M = {(x2, y2), (x3, y1),(x1, y4)}。 （5）找到交替链（x4, y3）（由标记（x4），（*）回溯得），置M = {(x2, y2), (x3, y1),(x1, y4), (x4, y3)}。

（6）找到交替链（x5, y4, x1, y1, x3, y7）（如图9.5所示，图中各种线段的意义同上），因而得

M = {(x2, y2), (x4, y3),(x5, y4), (x1, y1), (x3, y 7)}

下面是几个练习题：

http://172.28.138.8:8080/acmhome/problemdetail.do?&method=showdetail&id=1387

1387 Guardian of Decency

题目给出一些boy和girl，有一些规则他们在一些条件下可能恋爱，求最多有多少人，他们之间不会恋爱，根据这样的规则构建一个二分图：boy和girl分两边,分别作为左右结点，根据规则如果满足可能恋爱的条件就连接，否则不连接，求出最大匹配，N-max_number_of_couples即为要求的结果。 实现代码：

#include #include #include using namespace std; typedef struct{ char sex; string str; int height; string sports; }People;