第5-4节 图的匹配

1、第四节 图的匹配页： 图表的标号，程序的注释一、什么是图的匹配1.图的定义无向图：无向图G是指非空有限集合VG，和VG中某些元素的无序对的集合EG，构成的二元组(VG，EG)。VG称为G的顶点集，其中的元素称为G的顶点。EG称为G的边集，其中的元素称为G的边。在不混淆的情况下，有时记VVG，EEG。如果Vv1,vn，那么E中的元素e与V中某两个元素构成的无序对(vi，vj)相对应，记evivj，或evjvi。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。二分图：设G是一个图。如果存在VG的一个划分X，Y，使得G的任何一条边的一个端点在X中，另一个端点在Y中，则称G为二分图

2、，记作G(X，Y，E)。如果G中X的每个顶点都与Y的每个顶点相邻，则称G为完全二分图。2.匹配的相关概念设G(V，E)是一个图，如果M不含环且任意两边都不相邻，则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。对于图G(V，E)，在每条边e上赋一个实数权w(e)。设M是G的一个匹配。定义，并称之为匹配M的权。G中权最大的匹配称为G的最大权匹配。如果对一切，eE，w(e)=1,则G的最大权匹配就是G的最大匹配。设M是图G=(V,E)的一个匹配，viV。若vi与M中的边相关联，则称vi是M饱和点，否则称vi为M非饱和点。如果G中每个顶点都是M饱和点，则称M为G的完美匹配。设M是G的一个匹配

3、，P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M交错链。类似地，我们可以定义G的交错圈。易知，G的交错圈一定是偶圈。一条连接两个不同的M非饱和点的M交错链称为M增广链。两个集合S1与S2的“异或”操作S1S2是指集合S1S2（S1S2）（S1S2）容易看出，设M是G的匹配，P是G中的M增广链、则MP也是G的匹配，而且。图表 1 “异或”操作可以证明，G中匹配M是最大匹配当且仅当G中没有M增广链。二、匹配算法1.二分图的最大匹配设有M个工人x1, x2, , xm，和N项工作y1, y2, , yn，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。由于种

4、种原因，每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。人员分配问题可以用图的语言来表述。令X=x1, x2, , xm，Y=y1, y2, ,yn，构造二分图G=(X, Y, E)如下：对于1im，1jn，当且仅当工人xi胜任工作yi时，G中有一条边xiyi，于是人员分配问题就成为在G中求一个最大匹配的问题。求最大匹配常用匈牙利算法，它的基本思想是：对于已知的匹配M，从X中的任一选定的M非饱和点出发，用标号法寻找M增广链。如果找到M增广链，则M就可以得到增广；否则从X中另一个M非饱和点出发，继续寻找M增广链。重复这个过程直到

5、G中不存在增广链结束，此时的匹配就是G的最大匹配。这个算法通常称为匈牙利算法，因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。图表 2 匈牙利算法理解了这个算法，就不难写出人员分配问题的解答了。在给出程序之前，先做一些假设：为了简单起见，假设工人数等于工作数，即N=M，且N100，这里，N也可以看作是二分图的|X|和|Y|。 数据从文件input.txt中读入，首先是N和|E|，下面|E|行每行两个数(I, J)，表示工人I可以胜任工作J，即二分图中的边xiyj。结果输出到文件output.txt，第一行是最大匹配数s，下面s行每行两个数(I, J)，表

6、示分配工人I做工作J，即匹配边xiyj。下面是人员分配问题的参考解答，该算法的时间复杂度为O(n3)。Program match;const maxn = 100;var map: array1 . maxn, 1 . maxn of boolean; 保存二分图 cover: array1 . maxn of boolean; 标记一个点是否为饱和点 link: array1 . maxn of integer; 保存匹配边 n: integer; 顶点数procedure init; 读入var i, e, x, y: integer;begin assign(input, 'in

7、put.txt'); reset(input); readln(n, e); for i := 1 to e do begin readln(x, y); mapx, y := true; end; close(input);end;function find(i: integer): boolean; 从i出发，找增广链var k, q: integer;begin find := true; for k := 1 to n do if mapi, k and not coverk then begin q := linkk; linkk := i; coverk := true;

8、if (q = 0) or find(q) then exit; linkk := q; end; find := false;end;procedure main; 求匹配var i: integer;begin for i := 1 to n do begin fillchar(cover, sizeof(cover), 0); find(i); end;end;procedure print; 输出var i, s: integer;begin assign(output, 'output.txt'); rewrite(output); s := 0; for i :=

9、1 to n do if linki <> 0 then s := s + 1; writeln(s); for i := 1 to n do if linki <> 0 then writeln(linki, ' ', i); close(output);end;begin init; main; print;end.2.二分图的最大权匹配对于上面的人员分配问题，如果还考虑到工人做工的效率，就可以提出所谓的分派问题：应该怎样分配才能使总的效率最大？同上一节，我们可以构造一个二分图G，如果把工人xi做工作yi的效率wij看作是G中边xiyi的权，则分派问

10、题就相当于在赋权二分图G中求一个最大全匹配。由线性规划的知识，求二分图G的最大权匹配，只需在匈牙利算法的基础上少许改进即可。它的基本思想是，对二分图的顶点编号，然后根据编号构造一个新的二分图G，最后把求G的最大权匹配转换为求G的完美匹配。下面的这条定理是这个算法的理论基础。定理：设是赋权图（权非负）的完全二分图的一个完美匹配，这里。如果存在一组，满足，并且对一切，均有，则是的最大权匹配。下面，给出求最大权匹配的程序。输入文件中首先是N和|E|，下面|E|行每行三个数(I, J, W)，表示工人I做工作J的效率是W。程序输出包括每个工人的选择和最后的总效益。其它假设参见上一节的算法假设。这个算法

11、的时间复杂度也是O(n3)。Program maxmatch;const maxn = 100;var map: array1 . maxn, 1 . maxn of integer; 保存二分图 link, lx, ly: array1 . maxn of integer; 保存匹配边和每个点的标号 x, y: array1 . maxn of boolean; 标记一个点是否为饱和点 n: integer; 顶点数procedure init; 读入var i, e, x, y: integer;begin assign(input, 'input.txt'); reset

12、(input); readln(n, e); for i := 1 to e do readln(x, y, mapx, y); close(input);end;function find(v: integer): boolean; 从v出发，找增广链var i, k: integer;begin find := true; xv := true; for i := 1 to n do if not yi and (lxv + lyi = mapv, i) then begin yi := true; k := linki; linki := v; if (k = 0) or find(k)

13、 then exit; linki := 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 mapi, j > lxi then lxi := mapi, j; for k := 1 to n do repeat fillchar(x, sizeof(x), 0); fillchar(y,

14、 sizeof(y), 0); if find(k) then break; d := maxint; for i := 1 to n do if xi then for j := 1 to n do if not yj then if lxi + lyj - mapi, j < d then d := lxi + lyj - mapi, j; for i := 1 to n do if xi then lxi := lxi - d; for i := 1 to n do if yi then lyi := lyi + d; until false;end;procedure print

15、; 输出var i, s: integer;begin assign(output, 'output.txt'); rewrite(output); s := 0; for i := 1 to n do s := s + maplinki, i; writeln(s); close(output);end;begin init; main; print;end.3. 任意图的匹配任意图的最大匹配算法也是建立在找增广链的基础上的，只是任意图的增广链要比二分图难找得多。这个算法比较复杂，竞赛中也很少用到，因此，这里就不做详细介绍了。三、匹配的应用1. 匹配与一一对应问题：FJOI-

16、信封问题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，尽可能多地将信正确地装回信封。其中n100。例如，有4封信，而且第一封信不是装在信封1、2和3中，第2封信不是装在信封2和3中，则可以确定的第一封信装在信封4中，而且第二封信则装在信封1中。但这些

17、条件还不足以确定第三封和第四封信的位置。分析：看了这道题目，感觉上和小学数学竞赛中的逻辑推理题如出一辙，而逻辑推理题的做法一般是表上作业法。就以前面的例子为例，根据条件，可以得到如下信息：信封信12341×××2××34表格 1由于每一行每一列都应该只有一个，因此，可以确定第一封信装在信封4中，于是可以得到：信封信12341×××2×××3×4×表格 2然后，发现第二行有3个×,因此剩下一个肯定是，于是就可以得出第二封信则装在信封1中：信封信12341&#

18、215;××2×××3××4××表格 3现在，第3行和第4行都只有两个×，因此无法确定它们放在那个信封里。这样我们就得到了一个初步的算法：在程序中建立一个二维表格，首先，根据条件填入若干个×，然后，检查所有还未确定的行和列，看有没有一行（列）中有n 1个×，如果没有，就结束；否则，把剩下的那一个空格填上，并且填了的那一行（列）的其它位置都填上×。这种方法虽然很容易想到，但却有针对这个方法的反例，例如：图表 3 一个反例图中上半部分的顶点表示“信”，下半部分的顶点表示

19、“信封”，如果信i可能放在信封j中，则在信i和信封j之间连一条边。由于每个顶点的度数都大于或等于2，即每行每列都至少有两个空位，故前面的算法无法进行任何推理，而事实却并非如此，比如说中间的那封信就只能放在中间的那个信封里。正是这个反例，使我们需要另辟蹊径。进一步分析可以发现，信和信封之间的关系，是一种一一对应的关系，这是因为一封信只能放到一个信封里，而一个信封也只能装一封信。而从信息学的角度来看，这种一一对应的关系，也可以看作是二分图的匹配关系。令X=x1, x2, , xm，Y=y1, y2, ,yn，构造二分图G=(X, Y, E)，当且仅当信i可以放到信封j中，G中存在边xiyj。这样，

20、任何一种信的分配方案，都可以看作是图G的一个完美匹配。例如上图就有且仅有如下两种完美匹配： 图表 4 所有的完美匹配由于中间的那条匹配边在两个完美匹配中都出现了，因此我们认为这条匹配边是“确定的”，换句话说，这条边所代表的关系也是确定的。容易看出，当且仅当对于G的所有完美匹配M，都存在一条匹配边xiyj，则可以确定信i可以放到信封j中。这样，我们就从匹配的角度建立了一个新的模型。那么，这个模型要如何求解呢？我们当然不能枚举出G所有的完美匹配，然后再去求它们边的交集这和搜索就没什么分别。在这里，我们需要对这个模型再做一个小小的转换：我们发现，条件“对于G的所有完美匹配M，都存在一条匹配边xiyj

21、”，等价于“如果图G存在完美匹配，而删除图G中的一条边xiyj得到的图G中却不存在完美匹配”。例如，左下图删除了一条“关键边”，故不存在完美匹配，而右下图删除的是一条“非关键边”，故存在完美匹配。 图表 5 删边的例子从表面上看，这个算法的时间复杂度似乎仍然很高。因为图G中最多有n2条边，每次试着删除一条边，又需要O(n3)的时间复杂度求一次完美匹配。总的复杂度高达O(n5)。实际上，我们可以先找到图G的一个完美匹配M，这样，删边就只需考虑匹配边了（因为删除非匹配边得到G，M仍然是G的完美匹配）。这样，只需删除n条边，时间复杂度就降到了O(n4)。再进一步分析，删除一条边以后，没有必要重新找完

22、美匹配，只需检查可不可以找到新的增广链就可以了。这样，时间复杂度就进一步降到了O(n3)。下面给出该题的参考程序。program letter;const finp = 'input.txt' fout = 'output.txt' maxn = 100;var n, x, y: integer; map: array1 . maxn, 1 . maxn of boolean; link, cover: array1 . maxn of integer;function path(i: integer): boolean; 找增广轨var k, p: integ

23、er;begin result := true; for k := 1 to n do if (coverk = 0) and mapi, k then begin p := linkk; linkk := i; coverk := 1; if (p = 0) or path(p) then exit; linkk := p; end; result := false;end;begin assign(input, finp); reset(input); assign(output, fout); rewrite(output); readln(n); fillchar(map, sizeo

24、f(map), true); repeat readln(x, y); if x + y = 0 then break; mapy, x := false; until false; fillchar(link, sizeof(link), 0); for x := 1 to n do begin fillchar(cover, sizeof(cover), 0); path(x); end; for x := 1 to n do begin y := linkx; linkx := 0; mapy, x := false; fillchar(cover, sizeof(cover), 0);

25、 if not path(y) then begin linkx := y; writeln(x, ' ', y); end; mapy, x := true; end; close(output); close(input);end.2. “完美”的最大权匹配问题：CTSC-丘比特的烦恼随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神月下老人，向他求教。月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他

26、没有找到。在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么它们所代表的人就会相爱无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人，选择的范围自然就小了很多，不能找到真正的有缘人。丘比特听了月下老人的解释，茅塞顿开，回去之后用了人间的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。这样，射中有缘人的机会也增加了不少。情人节(Valentine's day)的午夜零时，丘比特开始了自己的工作。他选择了一组数目相等的男女，感应到他们互相之间的缘分大小，并依次射出了神箭，使他们产生爱意。他希望能选择最好的方法，使被他选择的每一个人被射

27、中一次，且每一对被射中的人之间的缘分的和最大。当然，无论丘比特怎么改造自己的弓箭，总还是存在缺陷的。首先，弓箭的射程尽管增大了，但毕竟还是有限的，不能像月下老人那样，做到“千里姻缘一线牵”。其次，无论怎么改造，箭的轨迹终归只能是一条直线，也就是说，如果两个人之间的连线段上有别人，那么莫不可向他们射出丘比特之箭，否则，按月下老人的话，就是“乱点鸳鸯谱”了。作为一个凡人，你的任务是运用先进的计算机为丘比特找到最佳的方案。输入文件第一行为正整数k，表示丘比特之箭的射程，第二行为正整数n(n<30)，随后有2n行，表示丘比特选中的人的信息，其中前n行为男子，后n行为女子。每个人的信息由两部分组成

28、：他的姓名和他的位置。姓名是长度小于20且仅包含字母的字符串，忽略大小写的区别，位置是由一对整数表示的坐标，它们之间用空格分隔。格式为Name x y。输入文件剩下的部分描述了这些人的缘分。每一行的格式为Name1 Name2 p。Name1和Name2为有缘人的姓名，p是他们之间的缘分值(p为小于等于255的正整数)。以一个End作为文件结束标志。每两个人之间的缘分至多只被描述一次。如果没有被描述，则说明他们缘分值为1。输出文件仅一个正整数，表示每一对被射中的人之间的缘分的总和。这个和应当是最大的。分析：题目中出现了三类物体和两种关系，我们一个个的来分析：丘比特的箭，它有一个属性是射程，男人

29、和女人，他们的属性包括名字和位置，男人和女人之间的关系，这个关系是他们俩的缘分值，箭与男女的关系，如果两人的距离不超过箭的射程，并无他人阻挡，则可能被箭射中。题目就是要求一种射箭的方案，使得所有被射中的男女的缘分和最大。这个问题很像是要求一个二分图的最大权匹配。因为男人和女人分属两个集合，而且同性之间没有任何关系，因此是一个二分图。而把缘分值记做边上的权，则缘分和最大，就对应了这个二分图中的一个最大权匹配。要注意的是，题目中虽然说明没有被描述的男女之间缘分值为1，但这并不代表所得到的二分图是完全二分图。因为在构图的过程中，我们必须还考虑到箭的射程等因素如果两人的距离超过了箭的射程，则他俩注定无

30、缘了。这时问题就来了，因为题目中除了要求缘分和最大之外，还要求“被丘比特选择的每一个人都要被射中一次”。你可能会觉得，要缘分和越大，当然被射中的人越多越好，其实并不是这样。例如：图表 6 一个反例如果要求最大权匹配，则会选择匹配边AD，缘分和为10。但由于每个人都要被射中一次，因此我们只能选择AC和BD，缘分和为2。换句话说，对于这个例子，正确答案应该是2，而最大权匹配的值却是10。这说明，这道题目和简单的最大权匹配还是有区别的，因为题目再要求权值最大的同时，还要求是一个完美匹配，我们称之为“完美”的最大权匹配。那么，这道题是否就不能用最大权匹配来做了呢？先别急，我们再来回顾一下求最大权匹配的

31、算法：我们通过对顶点编号, 将图G转化为G，然后在把求G的最大权匹配转换为求G的完美匹配这里好像就是求完美匹配，但对于上面的那个例子，又为什么不呢？原来，对于上面的例子，在标号过后，新的图G中加入了一条新的边BC，而这条边的权值是0，在图G中的完美匹配，实际上是AD和BC，对应到图G中，就是边AD了。因此，如果我们预先把BC的边的权值设为，再求图中的最大权匹配，就不会再有问题了。更一般的，如果要求二分图的“完美”的最大权匹配，只需将原图中没有的边的权值设为，就可以了。下面给出这道题目的程序。program cupid;const finp = 'cupid.in' fout =

32、 'cupid.out' maxn = 30;type Tperson = record x, y: integer; name: string; end; Tpersons = array1 . maxn of Tperson;var len, n, i, j, k, d: integer; line, nl, nr: string; man, woman: Tpersons; lx, ly, link: array1 . maxn of integer; map: array1 . maxn, 1 . maxn of byte; cx, cy: array1 . maxn

33、of boolean;function same(const A, B: string): boolean; 判断AB是否相等var i: integer;begin result := false; if length(A) <> length(B) then exit; for i := 1 to length(A) do if upcase(Ai) <> upcase(Bi) then exit; result := true;end;function find(const p: Tpersons; const name: string): integer; 找编

34、号begin result := n; while (result > 0) and not same(, name) do result := result - 1;end;function path(i: integer): boolean; 找增广轨var k, p: integer;begin result := true; cxi := true; for k := 1 to n do if not cyk and (mapi, k = lxi + lyk) and (mapi, k > 0) then begin cyk := true; p :

35、= linkk; linkk := i; if (p = 0) or path(p) then exit; linkk := p; end; result := false;end;function inside(A, B, P: Tperson): boolean; 判断P是否挡住ABbegin A.x := A.x - P.x; A.y := A.y - P.y; B.x := B.x - P.x; B.y := B.y - P.y; result := (A.x * B.y = A.y * B.x) and (A.x * B.x < 0) or (A.y * B.y < 0)

36、;end;begin assign(input, finp); reset(input); assign(output, fout); rewrite(output); readln(len, n); for i := 1 to n do readln(mani.x, mani.y, ); for i := 1 to n do readln(womani.x, womani.y, ); fillchar(map, sizeof(map), 1); repeat readln(line); if line = 'End' then brea

37、k; i := pos(' ', line); nl := ' ' + copy(line, 1, i - 1); delete(line, 1, i); i := pos(' ', line); nr := ' ' + copy(line, 1, i - 1); delete(line, 1, i); i := find(man, nl); j := find(woman, nr); if (i = 0) or (j = 0) then begin i := find(man, nr); j := find(woman, nl)

38、; end; val(line, mapi, j, k); until false; for i := 1 to n do for j := 1 to n do begin if sqr(mani.x - womanj.x) + sqr(mani.y - womanj.y) > sqr(len) then mapi, j := 0; for k := 1 to n do if (i <> k) and inside(mani, womanj, mank) or (j <> k) and inside(mani, womanj, womank) then mapi,

39、 j := 0; end; fillchar(lx, sizeof(lx), 0); fillchar(ly, sizeof(ly), 0); for i := 1 to n do for j := 1 to n do if mapi, j > lxi then lxi := mapi, j; fillchar(link, sizeof(link), 0); for k := 1 to n do repeat fillchar(cx, sizeof(cx), 0); fillchar(cy, sizeof(cy), 0); if path(k) then break; d := maxi

40、nt; for i := 1 to n do if cxi then for j := 1 to n do if not cyj then if (mapi, j > 0) and (lxi + lyj - mapi, j < d) then d := lxi + lyj - mapi, j; for i := 1 to n do if cxi then lxi := lxi - d; for i := 1 to n do if cyi then lyi := lyi + d; until false; len := 0; for i := 1 to n do len := len

41、 + maplinki, i; writeln(len); close(output); close(input);end.3. 稀疏图的匹配问题：IPSC-Magic一个著名的魔术师上台表演，跟着他的是一位漂亮的女助手。魔术师先从他的魔术帽中拽出了几只兔子，接着他又从女助手的围巾中变出了一束鲜花，最后，他把女助手锁在一个看上去空着的箱子里。然后，魔术师选了一个观众来配合一个表演：他在一个桌子上摆出N张牌（所有N张牌两两不同，且N为奇数）。魔术师让这位自愿者走上讲台从中选出（N+1）/2张牌，其余的牌都在魔术师的帽子里永远的消失了。魔术师在选出的牌上方晃了晃手，接着他选出其中一张交给那一位自愿

42、者，自愿者向观众展示了手中的这张牌，随后又将其藏在自己的衣袋里。那位女助手从箱子里放出来后，来到桌前也在剩下的（N1）21张牌上方晃了晃手，马上就说出了自愿者衣袋中的是什么牌。这是为什么呢？我们先看一下下面这张表，这是N=5的情况：自愿者选的牌魔术师选的牌助手所看到的牌1，2，331，21，2，421，41，2，521，51，3，441，31，3，513，51，4，514，52，3，442，32，3，532，52，4，552，43，4，553，4表格 4其中，自愿者选的牌魔术师选的牌助手所看到的牌。表中包括了自愿者选牌的所有可能性，它们两两不同。而助手所看到的牌，也是两两不同的。首先，魔术师和

43、他的助手都要记住这张表。这样，当助手看到的牌是2，4时，她就可以肯定自愿者选的牌是2，4，5，且魔术师选的牌就是5。现在，告诉你n的值，要你求出这张表。其中n15。分析：为了便于分析，我们令M表示从N张牌中选取（N1）2张牌的方案数，显然，从这N张牌中选出（N1）21张牌的方案数也是M。我们先从枚举的角度入手，下面给出两种枚举的方法：对于自愿者的每种选牌的方案，枚举魔术师所选的牌。对于自愿者的每种选牌的方案，所对应的助手看到的牌。方案一需要M次决策，每次决策中有N种选择；方案二同样需要M次决策，而每次决策的可以有M种选择。从这点上来看，方案一要好得多。、可是方案一所表现出来的“自愿者的选牌的方

44、案”和“魔术师所选的牌”之间的关系并不是一一对应的关系，对于自愿者不同的选牌的方案，魔术师可以选择相同的牌。而方案二中所表现出的关系正是一一对应的关系，因为题目要求对于自愿者不同的选牌的方案，助手看到的牌必须不同。前面已经提到过，从信息学的角度来看，一一对应，也可以看作是一种二分图的匹配的关系。因此，方案二更容易让人联系到匹配。令X=自愿者的选牌的方案集，Y=助手看到的牌的集合，构造二分图G=(X, Y, E)，当且仅当时，G中存在边xiyj。这样，就把原问题转换成求图G的一个完美匹配。下面问题又来了。首先，二分图的顶点高达2M个，当N=15时，M接近8000，而求匹配的复杂度为O(M3)，这

45、样高的复杂度，如何能够承受？注意到这个图是一个稀疏图，一共只有MN条边。而稀疏二分图匹配的复杂度也可以表示成O(|V|×|E|)。因此，时间复杂度应该是O(M2N)，基本上可以承受了。另外，由于这是稀疏图，我们用邻接表来存储，则空间复杂度仅为O(NM)，同样可以承受。最后要说明的是，这道题目也可以用构造法以获得更好的效率，但不如匹配容易想到。具体的构造方法这里就不给出了，读者可以自己想一想。下面给出参考程序：program magic;const n = 15; half = (n + 1) shr 1; m = 8000;var map: array1 . m, 0 . half

46、of integer; link: array1 . m of integer; cover: array1 . m of boolean; bits: array1 . n of integer; index: array0 . 1 shl n - 1 of integer; i, sum: integer;procedure buildA(d, p, x: integer); 建图var i: integer;begin if d = half then begin sum := sum + 1; indexx := sum; exit; end; for i := p + 1 to n

47、do buildA(d + 1, i, x or bitsi);end;procedure buildB(d, p, x: integer); 建图var i, k: integer;begin if d > half then begin sum := sum + 1; mapsum, 0 := x; k := 0; for i := 1 to n do if x and bitsi <> 0 then begin k := k + 1; mapsum, k := indexx - bitsi; end; exit; end; for i := p + 1 to n do

48、buildB(d + 1, i, x xor bitsi);end;function path(i: integer): boolean; 找增广轨var k, p, v: integer;begin result := true; for k := 1 to half do begin v := mapi, k; if not coverv then begin p := linkv; linkv := i; coverv := true; if (p = 0) or path(p) then exit; linkv := p; end; end; result := false;end;p

49、rocedure show(d, p, x: integer); 输出var i, k: integer;begin if d = half then begin sum := sum + 1; k := maplinksum, 0 xor x; for i := 1 to n do if bitsi and (x + k) <> 0 then write(i, ' '); for i := 1 to n do if bitsi = k then writeln('-> ', i); exit; end; for i := p + 1 to n

50、 do show(d + 1, i, x xor bitsi);end;begin for i := 1 to n do bitsi := 1 shl (i - 1); sum := 0; buildA(1, 0, 0); sum := 0; buildB(1, 0, 0); fillchar(link, sizeof(link), 0); for i := 1 to sum do begin fillchar(cover, sizeof(cover), false); path(i); end; assign(output, 'output.txt'); rewrite(ou

51、tput); sum := 0; show(1, 0, 0); close(output);end.4. 最小最大匹配问题：OOPC-神秘之山M个人在追一只奇怪的小动物。眼看就要追到了，那小东西却一溜烟蹿上一座神秘的山。众人抬头望去那山看起来就是这个样子：图表 7 样例示意图那山由N1条线段组成。各个端点从左到右编号为0N1，即xi<xi1(0in)。而且有y0=yn1=0。根据经验来说那小东西极有可能藏在1N 中的某个端点。有趣的是大家很快发现了原来M恰好等于N，这样，他们决定每人选一个点，看看它是否在躲那里。一开始，他们都在山脚下，第i 个人的位置是（si, 0）。他们每人选择一个中

52、间点（xi, 0），先以速度wi水平走到那里，再一口气沿直线以速度ci爬到他的目的地。由于他们的数学不好，他们只知道如何选择一个最好的整数来作为中间点的横坐标xi。而且很明显，路线的任何一个部分都不能在山的上方（他们又不会飞）。他们不希望这次再失败了，因此队长决定要寻找一个方案，使得最后一个到达目的地的人尽量早点到。他们该怎么做呢？其中1N100，0xi, yi, si1000，1ci<wi100。输入第一行包含一个整数N。以下N+2行每行，包含两个整数xi和yi，代表相应端点的坐标。以下N行每行包含3个整数：ci, wi和si，代表第i个人的爬山速度，行走速度和初始位置输出输出最后一个

53、人到达目的地的最早可能时间，四舍五入到小数点后两位。样例输入30 03 46 112 616 02 4 48 10 154 25 14样例输出1.43样例说明在这里例子中，第一个人先到（5, 0）再爬到端点2；第二个人直接爬到端点3；第三个人先到（4, 0）再爬到端点1。如下图：图表 8 样例的解答分析：题目中的数据繁多复杂，我们先把他们提出来一个个分析：人，共n个，与之有关的有初始横坐标s，速度w和c山头，共n个，与之有关的有坐标x和y根据这些信息，可以得到，人和山头的关系：tI, J，表示第i个人到达山头j所需的最短时间。题目中已经指明是一个人负责一个山头，这显然是一个一一对应的关系，因此，我们可以从二分图的匹配的角度来考虑这个问题。那么，这道题目属于哪一种匹配呢？是简单的