匈牙利算法分析和总结.docx

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

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

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

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

i i i

去标记Y中顶点y。重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。

i选取一个刚标记（在步骤(2)中用(xi)标记）过的Y中结点，例如y

i

，如果y

与x为

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

i

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

标记到一个Y中顶点y，它不是M顶点。这时从y出发循标记回溯，直到（*）标记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。

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

当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有标记。

对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止(算法找不到交替链).

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

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

（1） 置M=空，对x-x

1 6

标记（*）。

11（2）找到交替链（x1,y）（由标记（x

1

1

），（*）回溯得），置M={(x

,y)}。

1121(3)找到交替链（x2,y2）（由标记（x

1

1

2

1

），（*）回溯得），置M={(x

,y),(x,y),}。

122

1

2

（

（4）找到交替链（x,y,x,y）（如图9.4所示。图中虚线表示非匹配边，细实线表示

3 1 1 4

交替链中非匹配边，粗实线表示匹配边），因而得M={(x,y),(x,y),(x,y)}。

2 2

3 1 1 4

（5）找到交替链（x,y）（由标记（x），（*）回溯得），置M={(x,y),(x,y),

4 3

4

2 2

3 1

(x,y),(x,y)}。

1 4

4 3

（6）找到交替链（x,y,x,y,x,y）（如图9.5所示，图中各种线段的意义同上），

5 4 1 1 3 7

因而得

M={(x2,y2),(x4,y3),(x5,y4),(x1,y1),

(x3,y7)}

下面是几个练习题：:8080/acmhome/problemdetail.do?method=showdetailid=13871387GuardianofDecency

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

实现代码：#includeiostream#includestring#includecmathusingnamespacestd;typedefstruct{

charsex;stringstr;intheight;

stringsports;

}People;

Peoplep[505];intn;

intpx[505],py[505];intmap[505][505];intflag[505];

intcheck(inti,intj){

if(abs(p[i].height-p[j].height)=40p[i].sex!=p[j].sexp[i].pare(p[j].str)==0p[i].pare(p[j].sports)!=0)return1;

return0;

}