图的匹配--匈牙利算法与KM算法
图的匹配
一、什么是图的匹配
1.图的定义
无向图:无向图G是指非空有限集合VG,和VG中某些元素的无序对的集合EG,构成的二元组(VG,EG)。VG称为G的顶点集,其中的元素称为G的顶点。EG称为G的边集,其中的元素称为G的边。在不混淆的情况下,有时记V=VG,E=EG。如果V={v1,„,vn},那么E中的元素e与V中某两个元素构成的无序对(vi,vj)相对应,记e=vivj,或e=vjvi。在分析问题时,我们通常可以用小圆圈表示顶点,用小圆圈之的连线表示边。
二分图:设G是一个图。如果存在VG的一个划分X,Y,使得G的任何一条边的一个端点在X中,另一个端点在Y中,则称G为二分图,记作G=(X,Y,E)。如果G中X的每个顶点都与Y的每个顶点相邻,则称G为完全二分图。
2.匹配的相关概念
设G=(V,E)是一个图,ME,如果M不含环且任意两边都不相邻,则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。
对于图G=(V,E),在每条边e上赋一个实数权w(e)。设M是G的一个匹配。定义w(M)w(e),并称之为匹配M的权。G中权最大的匹配称为G的最大权匹配。如果
em
对一切,e∈E,w(e)=1,则G的最大权匹配就是G的最大匹配。
设M是图G=(V,E)的一个匹配,vi∈V。若vi与M中的边相关联,则称vi是M饱和点,否则称vi为M非饱和点。
如果G中每个顶点都是M饱和点,则称M为G的完美匹配。
设M是G的一个匹配,P是G的一条链。如果P的边交替地一条是M中的边,一条不是M中的边,则称P为M交错链。类似地,我们可以定义G的交错圈。易知,G的交错圈一定是偶圈。
一条连接两个不同的M非饱和点的M交错链称为M增广链。
两个集合S1与S2的“异或”操作S1⊕S2是指集合S1⊕S2=(S1∩S2)\(S1∪S2) 容易看出,设M是G的匹配,P是G中的M增广链、则M⊕P也是G的匹配,而且MPM1。
图表 1 “异或”操作
可以证明,G中匹配M是最大匹配当且仅当G中没有M增广链。
二、匹配算法
1.二分图的最大匹配
设有M个工人x1, x2, …, xm,和N项工作y1, y2, …, yn,规定每个工人至多做一项工作,而每项工作至多分配一名工人去做。由于种种原因,每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。
人员分配问题可以用图的语言来表述。令X={x1, x2, …, xm},Y={y1, y2, …,yn},构造二分图G=(X, Y, E)如下:
对于1≤i≤m,1≤j≤n,当且仅当工人xi胜任工作yi时,G中有一条边xiyi,于是人员分配问题就成为在G中求一个最大匹配的问题。
求最大匹配常用匈牙利算法,它的基本思想是:对于已知的匹配M,从X中的任一选定的M非饱和点出发,用标号法寻找M增广链。如果找到M增广链,则M就可以得到增广;否则从X中另一个M非饱和点出发,继续寻找M增广链。重复这个过程直到G中不存在增广链结束,此时的匹配就是G的最大匹配。这个算法通常称为匈牙利算法,因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。
图表 2 匈牙利算法
理解了这个算法,就不难写出人员分配问题的解答了。在给出程序之前,先做一些假设:
为了简单起见,假设工人数等于工作数,即N=M,且N≤100,这里,N也可以看作是二分图的|X|和|Y|。
数据从文件input.txt中读入,首先是N和|E|,下面|E|行每行两个数(I, J),表示工人I可以胜任工作J,即二分图中的边xiyj。
结果输出到文件output.txt,第一行是最大匹配数s,下面s行每行两个数(I, J),表示分配工人I做工作J,即匹配边xiyj。
下面是人员分配问题的参考解答,该算法的时间复杂度为O(n3)。
Program match; const
maxn = 100; var
map: array[1 .. maxn, 1 .. maxn] of boolean; {保存二分图}
cover: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} link: array[1 .. maxn] of integer; {保存匹配边} n: integer; {顶点数}
procedure init; {读入} var
i, e, x, y: integer; begin
assign(input, 'input.txt'); reset(input); readln(n, e);
for i := 1 to e do begin
readln(x, y); map[x, 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 map[i, k] and not cover[k] then begin q := link[k]; link[k] := i; cover[k] := true; if (q = 0) or find(q) then exit; link[k] := 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 := 1 to n do if link[i] 0 then s := s + 1; writeln(s);
for i := 1 to n do if link[i] 0 then writeln(link[i], ' ', i); close(output); end;
begin init; main; print; end.
2.二分图的最大权匹配
对于上面的人员分配问题,如果还考虑到工人做工的效率,就可以提出所谓的分派问题:应该怎样分配才能使总的效率最大?
同上一节,我们可以构造一个二分图G,如果把工人xi做工作yi的效率wij看作是G中边xiyi的权,则分派问题就相当于在赋权二分图G中求一个最大全匹配。
由线性规划的知识,求二分图G的最大权匹配,只需在匈牙利算法的基础上少许改进
’
即可。它的基本思想是,对二分图的顶点编号,然后根据编号构造一个新的二分图G,最
’
后把求G的最大权匹配转换为求G的完美匹配。
下面的这条定理是这个算法的理论基础。
定理:设M是赋权图(权非负)的完全二分图G(X,Y,E,w)的一个完美匹配,这里X。如果存在一组{i,j},满足ijwij,(i,j1,2,,n),并且对一切
xiyjM,均有ijwij,则M是G的最大权匹配。
下面,给出求最大权匹配的程序。输入文件中首先是N和|E|,下面|E|行每行三个数(I, J, W),表示工人I做工作J的效率是W。程序输出包括每个工人的选择和最后的总效益。其它假设参见上一节的算法假设。这个算法的时间复杂度也是O(n3)。
Program maxmatch; const
maxn = 100; var
map: array[1 .. maxn, 1 .. maxn] of integer; {保存二分图}
link, lx, ly: array[1 .. maxn] of integer; {保存匹配边和每个点的标号} x, y: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} n: integer; {顶点数}
procedure init; {读入} var
i, e, x, y: integer; begin
assign(input, 'input.txt'); reset(input);
for i := 1 to e do readln(x, y, map[x, y]); close(input); end;
function find(v: integer): boolean; {从v出发,找增广链} 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]
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;
procedure print; {输出} var
i, s: integer; begin
assign(output, 'output.txt'); rewrite(output); s := 0;
for i := 1 to n do s := s + map[link[i], i];
close(output); end;
begin init; main; print; end.
3. 任意图的匹配
任意图的最大匹配算法也是建立在找增广链的基础上的,只是任意图的增广链要比二分图难找得多。这个算法比较复杂,竞赛中也很少用到,因此,这里就不做详细介绍了。 三、匹配的应用
1. 匹配与一一对应
问题: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中。但这些条件还不足以确定第三封和第四封信的位置。
分析:
看了这道题目,感觉上和小学数学竞赛中的逻辑推理题如出一辙,而逻辑推理题的做法一般是表上作业法。
就以前面的例子为例,根据条件,可以得到如下信息:
由于每一行每一列都应该只有一个√,因此,可以确定第一封信装在信封4中,于是可以得到:
然后,发现第二行有3个×,因此剩下一个肯定是√,于是就可以得出第二封信则装在信封1中:
现在,第3行和第4行都只有两个×,因此无法确定它们放在那个信封里。
这样我们就得到了一个初步的算法:在程序中建立一个二维表格,首先,根据条件填入若干个×,然后,检查所有还未确定的行和列,看有没有一行(列)中有n – 1个×,如果没有,就结束;否则,把剩下的那一个空格填上√,并且填了√的那一行(列)的其它位置都填上×。
这种方法虽然很容易想到,但却有针对这个方法的反例,例如:
图表 3 一个反例
图中上半部分的顶点表示“信”,下半部分的顶点表示“信封”,如果信i可能放在信封j中,则在信i和信封j之间连一条边。由于每个顶点的度数都大于或等于2,即每行每列都至少有两个空位,故前面的算法无法进行任何推理,而事实却并非如此,比如说中间的那封信就只能放在中间的那个信封里。
正是这个反例,使我们需要另辟蹊径。进一步分析可以发现,信和信封之间的关系,是一种一一对应的关系,这是因为一封信只能放到一个信封里,而一个信封也只能装一封信。而从信息学的角度来看,这种一一对应的关系,也可以看作是二分图的匹配关系。
令X={x1, x2, …, xm},Y={y1, y2, …,yn},构造二分图G=(X, Y, E),当且仅当信i可以
放到信封j中,G中存在边xiyj。这样,任何一种信的分配方案,都可以看作是图G的一个完美匹配。例如上图就有且仅有如下两种完美匹配:
图表 4 所有的完美匹配
由于中间的那条匹配边在两个完美匹配中都出现了,因此我们认为这条匹配边是“确定的”,换句话说,这条边所代表的关系也是确定的。容易看出,当且仅当对于G的所有完美匹配M,都存在一条匹配边xiyj,则可以确定信i可以放到信封j中。
这样,我们就从匹配的角度建立了一个新的模型。那么,这个模型要如何求解呢? 我们当然不能枚举出G所有的完美匹配,然后再去求它们边的交集——这和搜索就没什么分别。在这里,我们需要对这个模型再做一个小小的转换:我们发现,条件“对于G的所有完美匹配M,都存在一条匹配边xiyj”,等价于“如果图G存在完美匹配,而删除
’
图G中的一条边xiyj得到的图G中却不存在完美匹配”。例如,左下图删除了一条“关键边”,故不存在完美匹配,而右下图删除的是一条“非关键边”,故存在完美匹配。
图表 5 删边的例子
从表面上看,这个算法的时间复杂度似乎仍然很高。因为图G中最多有n2条边,每
35
次试着删除一条边,又需要O(n)的时间复杂度求一次完美匹配。总的复杂度高达O(n)。
实际上,我们可以先找到图G的一个完美匹配M,这样,删边就只需考虑匹配边了(因
’’
为删除非匹配边得到G,M仍然是G的完美匹配)。这样,只需删除n条边,时间复杂度
4
就降到了O(n)。
再进一步分析,删除一条边以后,没有必要重新找完美匹配,只需检查可不可以找到新的增广链就可以了。这样,时间复杂度就进一步降到了O(n3)。
下面给出该题的参考程序。
program letter;
const
finp = 'input.txt'; fout = 'output.txt'; maxn = 100; var
n, x, y: integer;
map: array[1 .. maxn, 1 .. maxn] of boolean;
link, cover: array[1 .. maxn] of integer;
function path(i: integer): boolean; {找增广轨} var
k, p: integer; begin
result := true; for k := 1 to n do
if (cover[k] = 0) and map[i, k] then begin p := link[k]; link[k] := i; cover[k] := 1; if (p = 0) or path(p) then exit; link[k] := p; end;
result := false; end;
begin
assign(input, finp); reset(input); assign(output, fout); rewrite(output); readln(n);
fillchar(map, sizeof(map), true); repeat
readln(x, y);
if x + y = 0 then break; map[y, 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 := link[x]; link[x] := 0;
map[y, x] := false; fillchar(cover, sizeof(cover), 0); if not path(y) then begin
link[x] := y; writeln(x, ' ', y); end;
map[y, x] := true; end;
close(output); close(input); end.
2. “完美”的最大权匹配
问题:CTSC-丘比特的烦恼
随着社会的不断发展,人与人之间的感情越来越功利化。最近,爱神丘比特发现,爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼,他越来越难找到合适的男女,并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国,找到了掌管东方人爱情的神——月下老人,向他求教。
月下老人告诉丘比特,纯洁的爱情并不是不存在,而是他没有找到。在东方,人们讲
究的是缘分。月下老人只要做一男一女两个泥人,在他们之间连上一条红线,那么它们所代表的人就会相爱——无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人,选择的范围自然就小了很多,不能找到真正的有缘人。
丘比特听了月下老人的解释,茅塞顿开,回去之后用了人间的最新科技改造了自己的弓箭,使得丘比特之箭的射程大大增加。这样,射中有缘人的机会也增加了不少。
情人节(Valentine's day)的午夜零时,丘比特开始了自己的工作。他选择了一组数目相等的男女,感应到他们互相之间的缘分大小,并依次射出了神箭,使他们产生爱意。他希望能选择最好的方法,使被他选择的每一个人被射中一次,且每一对被射中的人之间的缘分的和最大。
当然,无论丘比特怎么改造自己的弓箭,总还是存在缺陷的。首先,弓箭的射程尽管增大了,但毕竟还是有限的,不能像月下老人那样,做到“千里姻缘一线牵”。其次,无论怎么改造,箭的轨迹终归只能是一条直线,也就是说,如果两个人之间的连线段上有别人,那么莫不可向他们射出丘比特之箭,否则,按月下老人的话,就是“乱点鸳鸯谱”了。
作为一个凡人,你的任务是运用先进的计算机为丘比特找到最佳的方案。
输入文件第一行为正整数k,表示丘比特之箭的射程,第二行为正整数n(n
输出文件仅一个正整数,表示每一对被射中的人之间的缘分的总和。这个和应当是最大的。
分析:
题目中出现了三类物体和两种关系,我们一个个的来分析: 丘比特的箭,它有一个属性是射程,
男人和女人,他们的属性包括名字和位置,
男人和女人之间的关系,这个关系是他们俩的缘分值, 箭与男女的关系,如果两人的距离不超过箭的射程,并无他人阻挡,则可能被箭射中。题目就是要求一种射箭的方案,使得所有被射中的男女的缘分和最大。
这个问题很像是要求一个二分图的最大权匹配。因为男人和女人分属两个集合,而且同性之间没有任何关系,因此是一个二分图。而把缘分值记做边上的权,则缘分和最大,就对应了这个二分图中的一个最大权匹配。
要注意的是,题目中虽然说明没有被描述的男女之间缘分值为1,但这并不代表所得到的二分图是完全二分图。因为在构图的过程中,我们必须还考虑到箭的射程等因素——如果两人的距离超过了箭的射程,则他俩注定无缘了。
这时问题就来了,因为题目中除了要求缘分和最大之外,还要求“被丘比特选择的每一个人都要被射中一次”。
你可能会觉得,要缘分和越大,当然被射中的人越多越好,其实并不是这样。例如:
图表 6 一个反例
如果要求最大权匹配,则会选择匹配边AD,缘分和为10。但由于每个人都要被射中一次,因此我们只能选择AC和BD,缘分和为2。
换句话说,对于这个例子,正确答案应该是2,而最大权匹配的值却是10。这说明,这道题目和简单的最大权匹配还是有区别的,因为题目再要求权值最大的同时,还要求是一个完美匹配,我们称之为“完美”的最大权匹配。
那么,这道题是否就不能用最大权匹配来做了呢?先别急,我们再来回顾一下求最大
’
权匹配的算法:我们通过对顶点编号, 将图G转化为G,然后在把求G的最大权匹配转换为求G’的完美匹配——这里好像就是求完美匹配,但对于上面的那个例子,又为什么不呢?
原来,对于上面的例子,在标号过后,新的图G’中加入了一条新的边BC,而这条边
’
的权值是0,在图G中的完美匹配,实际上是AD和BC,对应到图G中,就是边AD了。
因此,如果我们预先把BC的边的权值设为-∞,再求图中的最大权匹配,就不会再有问题了。
更一般的,如果要求二分图的“完美”的最大权匹配,只需将原图中没有的边的权值设为-∞,就可以了。
下面给出这道题目的程序。
program cupid;
const
finp = 'cupid.in'; fout = 'cupid.out'; maxn = 30; type
Tperson = record x, y: integer; name: string; end;
Tpersons = array[1 .. maxn] of Tperson; var
len, n, i, j, k, d: integer; line, nl, nr: string;
man, woman: Tpersons;
lx, ly, link: array[1 .. maxn] of integer; map: array[1 .. maxn, 1 .. maxn] of byte; cx, cy: array[1 .. maxn] 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(A[i]) upcase(B[i]) then exit; result := true; end;
function find(const p: Tpersons; const name: string): integer; {找编号} begin
result := n;
while (result > 0) and not same(p[result].name, name) do result := result - 1; end;
function path(i: integer): boolean; {找增广轨} var
k, p: integer; begin
result := true; cx[i] := true; for k := 1 to n do
if not cy[k] and (map[i, k] = lx[i] + ly[k]) and (map[i, k] > 0) then begin cy[k] := true; p := link[k]; link[k] := i; if (p = 0) or path(p) then exit; link[k] := p; end;
result := false; end;
function inside(A, B, P: Tperson): boolean; {判断P是否挡住AB} begin
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
begin
assign(input, finp); reset(input); assign(output, fout); rewrite(output); readln(len, n);
for i := 1 to n do readln(man[i].x, man[i].y, man[i].name);
for i := 1 to n do readln(woman[i].x, woman[i].y, woman[i].name); fillchar(map, sizeof(map), 1); repeat
readln(line);
if line = 'End' then break;
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); end;
val(line, map[i, j], k); until false;
for i := 1 to n do for j := 1 to n do begin
if sqr(man[i].x - woman[j].x) + sqr(man[i].y - woman[j].y) > sqr(len) then map[i, j] := 0; for k := 1 to n do
if (i k) and inside(man[i], woman[j], man[k]) or
(j k) and inside(man[i], woman[j], woman[k]) then map[i, 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 map[i, j] > lx[i] then lx[i] := map[i, 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 := maxint;
for i := 1 to n do if cx[i] then for j := 1 to n do if not cy[j] then if (map[i, j] > 0) and (lx[i] + ly[j] - map[i, j]
for i := 1 to n do if cx[i] then lx[i] := lx[i] - d; for i := 1 to n do if cy[i] then ly[i] := ly[i] + d; until false;
len := 0; for i := 1 to n do len := len + map[link[i], i]; writeln(len);
close(output); close(input); end.
3. 稀疏图的匹配
问题:IPSC-Magic
一个著名的魔术师上台表演,跟着他的是一位漂亮的女助手。魔术师先从他的魔术帽中拽出了几只兔子,接着他又从女助手的围巾中变出了一束鲜花,最后,他把女助手锁在一个看上去空着的箱子里。然后,魔术师选了一个观众来配合一个表演:他在一个桌子上摆出N张牌(所有N张牌两两不同,且N为奇数)。魔术师让这位自愿者走上讲台从中选出(N+1)/2张牌,其余的牌都在魔术师的帽子里永远的消失了。魔术师在选出的牌上方晃了晃手,接着他选出其中一张交给那一位自愿者,自愿者向观众展示了手中的这张牌,随后又将其藏在自己的衣袋里。那位女助手从箱子里放出来后,来到桌前也在剩下的(N+1)/2-1张牌上方晃了晃手,马上就说出了自愿者衣袋中的是什么牌。
表格 4
其中,自愿者选的牌-魔术师选的牌=助手所看到的牌。表中包括了自愿者选牌的所有可能性,它们两两不同。而助手所看到的牌,也是两两不同的。
首先,魔术师和他的助手都要记住这张表。这样,当助手看到的牌是2,4时,她就可以肯定自愿者选的牌是2,4,5,且魔术师选的牌就是5。
现在,告诉你n的值,要你求出这张表。其中n≤15。
分析:
为了便于分析,我们令M表示从N张牌中选取(N+1)/2张牌的方案数,显然,从这N张牌中选出(N+1)/2-1张牌的方案数也是M。
我们先从枚举的角度入手,下面给出两种枚举的方法: 对于自愿者的每种选牌的方案,枚举魔术师所选的牌。 对于自愿者的每种选牌的方案,所对应的助手看到的牌。
方案一需要M次决策,每次决策中有N种选择;方案二同样需要M次决策,而每次决策的可以有M种选择。从这点上来看,方案一要好得多。、
可是方案一所表现出来的“自愿者的选牌的方案”和“魔术师所选的牌”之间的关系并不是一一对应的关系,对于自愿者不同的选牌的方案,魔术师可以选择相同的牌。
而方案二中所表现出的关系正是一一对应的关系,因为题目要求对于自愿者不同的选牌的方案,助手看到的牌必须不同。
前面已经提到过,从信息学的角度来看,一一对应,也可以看作是一种二分图的匹配的关系。因此,方案二更容易让人联系到匹配。
令X=自愿者的选牌的方案集,Y=助手看到的牌的集合,构造二分图G=(X, Y, E),当且仅当YjXi且XiYj1时,G中存在边xiyj。这样,就把原问题转换成求图G的一个完美匹配。
下面问题又来了。首先,二分图的顶点高达2M个,当N=15时,M接近8000,而求匹配的复杂度为O(M3),这样高的复杂度,如何能够承受?
注意到这个图是一个稀疏图,一共只有MN条边。而稀疏二分图匹配的复杂度也可以表示成O(|V|×|E|)。因此,时间复杂度应该是O(M2N),基本上可以承受了。
另外,由于这是稀疏图,我们用邻接表来存储,则空间复杂度仅为O(NM),同样可以承受。
最后要说明的是,这道题目也可以用构造法以获得更好的效率,但不如匹配容易想到。具体的构造方法这里就不给出了,读者可以自己想一想。
下面给出参考程序:
program magic;
const n = 15;
half = (n + 1) shr 1; m = 8000; var
map: array[1 .. m, 0 .. half] of integer; link: array[1 .. m] of integer; cover: array[1 .. m] of boolean; bits: array[1 .. n] of integer;
index: array[0 .. 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; index[x] := sum; exit; end;
for i := p + 1 to n do buildA(d + 1, i, x or bits[i]); end;
procedure buildB(d, p, x: integer); {建图} var
i, k: integer; begin
if d > half then begin
sum := sum + 1; map[sum, 0] := x; k := 0; for i := 1 to n do
if x and bits[i] 0 then begin
k := k + 1; map[sum, k] := index[x - bits[i]]; end; exit; end;
for i := p + 1 to n do buildB(d + 1, i, x xor bits[i]); end;
function path(i: integer): boolean; {找增广轨} var
k, p, v: integer; begin
result := true;
for k := 1 to half do begin v := map[i, k];
if not cover[v] then begin
p := link[v]; link[v] := i; cover[v] := true; if (p = 0) or path(p) then exit; link[v] := p; end; end;
result := false; end;
procedure show(d, p, x: integer); {输出} var
i, k: integer; begin
if d = half then begin
sum := sum + 1; k := map[link[sum], 0] xor x;
for i := 1 to n do if bits[i] and (x + k) 0 then write(i, ' '); for i := 1 to n do if bits[i] = k then writeln('-> ', i); exit; end;
for i := p + 1 to n do show(d + 1, i, x xor bits[i]); end;
begin
for i := 1 to n do bits[i] := 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(output); sum := 0; show(1, 0, 0); close(output); end.
4. 最小最大匹配
问题:OOPC-神秘之山
M个人在追一只奇怪的小动物。眼看就要追到了,那小东西却一溜烟蹿上一座神秘的山。众人抬头望去那山看起来就是这个样子:
图表 7 样例示意图
那山由N+1条线段组成。各个端点从左到右编号为0…N+1,即x[i]
根据经验来说那小东西极有可能藏在1…N 中的某个端点。有趣的是大家很快发现了原来M恰好等于N,这样,他们决定每人选一个点,看看它是否在躲那里。
一开始,他们都在山脚下,第i 个人的位置是(s[i], 0)。他们每人选择一个中间点(x[i], 0),先以速度w[i]水平走到那里,再一口气沿直线以速度c[i]爬到他的目的地。由于他们的数学不好,他们只知道如何选择一个最好的整数来作为中间点的横坐标x[i]。而且很明显,路线的任何一个部分都不能在山的上方(他们又不会飞)。
他们不希望这次再失败了,因此队长决定要寻找一个方案,使得最后一个到达目的地的人尽量早点到。他们该怎么做呢?
其中1≤N≤100,0≤x[i], y[i], s[i]≤1000,1≤c[i]
输入
第一行包含一个整数N。以下N+2行每行,包含两个整数xi和yi,代表相应端点的坐标。以下N行每行包含3个整数:ci, wi和si,代表第i个人的爬山速度,行走速度和初始位置
输出
输出最后一个人到达目的地的最早可能时间,四舍五入到小数点后两位。
样例输入
3 0 0 3 4 6 1 12 6 16 0 2 4 4 8 10 15 4 25 14 样例输出 1.43
样例说明
在这里例子中,第一个人先到(5, 0)再爬到端点2;第二个人直接爬到端点3;第三个人先到(4, 0)再爬到端点1。如下图:
图表 8 样例的解答
分析:
题目中的数据繁多复杂,我们先把他们提出来一个个分析: 人,共n个,与之有关的有初始横坐标s,速度w和c 山头,共n个,与之有关的有坐标x和y
根据这些信息,可以得到,人和山头的关系:t[I, J],表示第i个人到达山头j所需的最短时间。
题目中已经指明是一个人负责一个山头,这显然是一个一一对应的关系,因此,我们可以从二分图的匹配的角度来考虑这个问题。
那么,这道题目属于哪一种匹配呢?是简单的最大匹配,还是最大权匹配,或者是前面所提到的“完美”最大权匹配呢?
其实都不是。因为一般的最大权匹配,一个匹配的权的定义是该匹配中所有边上权的和,而这道题目,一个匹配的权是指该匹配的边上权值的最大值。题目要求这个最大值最小,我们暂且称之为“最小最大匹配”。
直接求解似乎不太方便。换一个角度,如果我们给出一个时间,就可以用完美匹配的算法来判断能否在这个时间内完成所有的工作。
’’
具体的来说,对于给定的二分图G和最大时间T,我们可以导出新的图G,G中所有边的权都不超过T。如果G’存在完美匹配,则所有工作可以在T时间内完成,否则则不能。
这样,一个简单的算法就诞生了:依次增加T,知道求出一个完美匹配为止。由于二分图中的边不会超过n2,因此T最多增加n2次,而每次增加T的值,需要O(n2)的时间来找增广链,这样总的时间复杂度就是O(n4)。
我们还可以采用二分查找的方法来寻找这个T,这样的算法时间复杂度就可以降到为3
O(nlogN)。 参考程序如下:
program mountain;
const
finp = 'input.txt'; fout = 'output.txt'; maxn = 100; var
i, k, d, p, m, n, ds, lo, hi: integer;
x, y, c, w, s, a, b, link: array[0 .. maxn + 1] of integer; len: array[1 .. maxn, 1 .. maxn] of integer; ls: array[1 .. maxn * maxn] of integer; cover: array[1 .. maxn] of boolean;
function path(i: integer): boolean; {找增广轨} var
k, p: integer; begin
result := true; for k := 1 to n do
if not cover[k] and (len[i, k]
result := false; end;
function update(k, i, p: integer; var v: integer): integer; {计算耗费} begin
result := round((abs(s[k] - p) / w[k] +
sqrt(sqr(p - x[i]) + sqr(y[i])) / c[k]) * 100); if (result
procedure sort(l, u: integer); {排序} var
i, j, k, x: integer; begin
i := l; j := u; x := ls[(i + j) div 2]; repeat
while ls[i] x do j := j - 1; if i
k := ls[i]; ls[i] := ls[j]; ls[j] := k; i := i + 1; j := j - 1; end; until i > j;
if l
begin
assign(input, finp); reset(input); assign(output, fout); rewrite(output); repeat
readln(n);
if n = 0 then break;
for i := 0 to n + 1 do readln(x[i], y[i]);
for i := 1 to n do readln(c[i], w[i], s[i]); for i := 1 to n do begin
a[i] := x[i] - x[0]; b[i] := x[n + 1] - x[i]; for k := 1 to n do begin
if y[k] >= y[i] then continue;
d := abs(y[i] * (x[k] - x[i]) div (y[i] - y[k])); if (k i) and (d
a[i] := x[i] - a[i]; b[i] := x[i] + b[i]; end;
m := 0; for k := 1 to n do
for i := 1 to n do begin len[k, i] := maxint;
ds := round(y[i] * c[k] / sqrt(sqr(w[k]) - sqr(c[k]))); if ds > abs(s[k] - x[i]) then ds := abs(s[k] - x[i]);
update(k, i, a[i], len[k, i]); update(k, i, b[i], len[k, i]); if s[k]
lo := 1; hi := m; sort(lo, hi); while lo
fillchar(link, sizeof(link), 0); fillchar(cover, sizeof(cover), 0); p := (lo + hi) div 2; ds := ls[p]; i := 1; while (i
i := i + 1; fillchar(cover, sizeof(cover), 0); end;
if i > n then hi := p else lo := p + 1; end;
writeln((ls[hi] / 100) : 0 : 2); until false;
close(input); close(output); end.