二分图的性质及km算法.ppt

流程(3) Gl中无完备匹配，故修改顶标。 流程(4) 根据新的顶标构造Gl ，并求其上的一个完全匹配如图所示： 图中粗点划线给出了一个最佳匹配，其最大权为4＋2＋4＋1＋3＝14。题目完成。 算法实现 定义如下变量 map: array[1 .. maxn, 1 .. maxn] of boolean; {保存二分图} link, lx, ly: array[1 .. maxn] of integer; {保存匹配边和每个点的标号} x, y: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} n: integer; {顶点数} 从v出发，找增广链 function find(v: integer): boolean; var i, k: integer; begin find := true; x[v] := true; for i := 1 to n do if not y[i] and (lx[v] + ly[i] = map[v, i]) then begin y[i] := true; k := link[i]; link[i] := v; if (k = 0) or find(k) then exit; link[i] := k; end; find := false; end; 求最大权匹配 procedure main; 　var i, j, k, d: integer; begin fillchar(lx, sizeof(lx), 0); fillchar(ly, sizeof(ly), 0); for i := 1 to n do 　　for j := 1 to n do if map[i, j] lx[i] then lx[i] := map[i, j]; for k := 1 to n do repeat fillchar(x, sizeof(x), 0); fillchar(y, sizeof(y), 0); if find(k) then break; d := maxint; for i := 1 to n do if x[i] then for j := 1 to n do if not y[j] then if lx[i] + ly[j] - map[i, j] d then d := lx[i] + ly[j] - map[i, j]; for i := 1 to n do if x[i] then lx[i] := lx[i] - d; for i := 1 to n do if y[i] then ly[i] := ly[i] + d; until false; end; 小结 偶图是一种特殊的图，所以它不但具备了信息量丰富这个图模型共有的优点，同时它也具备了大量一般图所不具备的内涵和算法优势。 偶图的结点分成两个部分，这就是它和自然界、数学界的对应关系，或者说匹配关系有着深刻的联系。因此，匹配的算法是所有偶图算法的核心。 如果能将实际问题，通过合理的抽象，变成两种事物之间的矛盾，则这种问题就可以抽象成偶图的模型。所以，偶图的模型有着广泛的应用。同时，偶图的算法有着高效实用的特点，所以也使通过偶图模型解决问题成为可能。 综上所述，偶图是一种高效的，有着广泛使用价值的模型。合理、有效的使用偶图模型，将大大提高编程及解决现实生活中实际问题的能力。 FJOI-信封问题 问题：John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。 将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。其中n≤100。 分析 看了这道题目，感觉上和小学数学竞赛中的逻辑推理题如出一辙，而逻辑推理题的做法一般是表上作业法。 就以前面的例子为例，根据条件，可以得到如下信息：例如，有4封信，而且第一封信不是装在信封1、2和3中，第2封信不是装在信封2和3中，则可以确定的第一封信装在信封4中，而且第二封信则装在信封1中。但这些条件还不足以确定第三封和第四封信的位置。 分析 由于每一行每一列都应该只有一个√，因此，可