第54節(jié) 圖的匹配

1、第四節(jié) 圖的匹配頁(yè)： 圖表的標(biāo)號(hào)，程序的注釋一、什么是圖的匹配1.圖的定義無(wú)向圖：無(wú)向圖G是指非空有限集合VG，和VG中某些元素的無(wú)序?qū)Φ募螮G，構(gòu)成的二元組(VG，EG)。VG稱為G的頂點(diǎn)集，其中的元素稱為G的頂點(diǎn)。EG稱為G的邊集，其中的元素稱為G的邊。在不混淆的情況下，有時(shí)記VVG，EEG。如果Vv1,vn，那么E中的元素e與V中某兩個(gè)元素構(gòu)成的無(wú)序?qū)?vi，vj)相對(duì)應(yīng)，記evivj，或evjvi。在分析問(wèn)題時(shí)，我們通?？梢杂眯A圈表示頂點(diǎn)，用小圓圈之的連線表示邊。二分圖：設(shè)G是一個(gè)圖。如果存在VG的一個(gè)劃分X，Y，使得G的任何一條邊的一個(gè)端點(diǎn)在X中，另一個(gè)端點(diǎn)在Y中，則稱G為二分圖

2、，記作G(X，Y，E)。如果G中X的每個(gè)頂點(diǎn)都與Y的每個(gè)頂點(diǎn)相鄰，則稱G為完全二分圖。2.匹配的相關(guān)概念設(shè)G(V，E)是一個(gè)圖，如果M不含環(huán)且任意兩邊都不相鄰，則稱M為G的一個(gè)匹配。G中邊數(shù)最多的匹配稱為G的最大匹配。對(duì)于圖G(V，E)，在每條邊e上賦一個(gè)實(shí)數(shù)權(quán)w(e)。設(shè)M是G的一個(gè)匹配。定義，并稱之為匹配M的權(quán)。G中權(quán)最大的匹配稱為G的最大權(quán)匹配。如果對(duì)一切，eE，w(e)=1,則G的最大權(quán)匹配就是G的最大匹配。設(shè)M是圖G=(V,E)的一個(gè)匹配，viV。若vi與M中的邊相關(guān)聯(lián)，則稱vi是M飽和點(diǎn)，否則稱vi為M非飽和點(diǎn)。如果G中每個(gè)頂點(diǎn)都是M飽和點(diǎn)，則稱M為G的完美匹配。設(shè)M是G的一個(gè)匹配

3、，P是G的一條鏈。如果P的邊交替地一條是M中的邊，一條不是M中的邊，則稱P為M交錯(cuò)鏈。類似地，我們可以定義G的交錯(cuò)圈。易知，G的交錯(cuò)圈一定是偶圈。一條連接兩個(gè)不同的M非飽和點(diǎn)的M交錯(cuò)鏈稱為M增廣鏈。兩個(gè)集合S1與S2的“異或”操作S1S2是指集合S1S2（S1S2）（S1S2）容易看出，設(shè)M是G的匹配，P是G中的M增廣鏈、則MP也是G的匹配，而且。圖表 1“異或”操作可以證明，G中匹配M是最大匹配當(dāng)且僅當(dāng)G中沒(méi)有M增廣鏈。二、匹配算法1.二分圖的最大匹配設(shè)有M個(gè)工人x1, x2, , xm，和N項(xiàng)工作y1, y2, , yn，規(guī)定每個(gè)工人至多做一項(xiàng)工作，而每項(xiàng)工作至多分配一名工人去做。由于種種

4、原因，每個(gè)工人只能勝任其中的一項(xiàng)或幾項(xiàng)工作。問(wèn)應(yīng)怎樣分配才能使盡可能多的工人分配到他勝任的工作。這個(gè)問(wèn)題稱為人員分配問(wèn)題。人員分配問(wèn)題可以用圖的語(yǔ)言來(lái)表述。令X=x1, x2, , xm，Y=y1, y2, ,yn，構(gòu)造二分圖G=(X, Y, E)如下：對(duì)于1im，1jn，當(dāng)且僅當(dāng)工人xi勝任工作yi時(shí)，G中有一條邊xiyi，于是人員分配問(wèn)題就成為在G中求一個(gè)最大匹配的問(wèn)題。求最大匹配常用匈牙利算法，它的基本思想是：對(duì)于已知的匹配M，從X中的任一選定的M非飽和點(diǎn)出發(fā)，用標(biāo)號(hào)法尋找M增廣鏈。如果找到M增廣鏈，則M就可以得到增廣；否則從X中另一個(gè)M非飽和點(diǎn)出發(fā)，繼續(xù)尋找M增廣鏈。重復(fù)這個(gè)過(guò)程直到G

5、中不存在增廣鏈結(jié)束，此時(shí)的匹配就是G的最大匹配。這個(gè)算法通常稱為匈牙利算法，因?yàn)檫@里介紹的尋找增廣鏈的標(biāo)號(hào)方法是由匈牙科學(xué)者Egerváry最早提出來(lái)的。圖表 2 匈牙利算法理解了這個(gè)算法，就不難寫出人員分配問(wèn)題的解答了。在給出程序之前，先做一些假設(shè)：為了簡(jiǎn)單起見(jiàn)，假設(shè)工人數(shù)等于工作數(shù)，即N=M，且N100，這里，N也可以看作是二分圖的|X|和|Y|。數(shù)據(jù)從文件input.txt中讀入，首先是N和|E|，下面|E|行每行兩個(gè)數(shù)(I, J)，表示工人I可以勝任工作J，即二分圖中的邊xiyj。結(jié)果輸出到文件output.txt，第一行是最大匹配數(shù)s，下面s行每行兩個(gè)數(shù)(I, J)，表示分

6、配工人I做工作J，即匹配邊xiyj。下面是人員分配問(wèn)題的參考解答，該算法的時(shí)間復(fù)雜度為O(n3)。Program match;const maxn = 100;var map: array1 . maxn, 1 . maxn of boolean; 保存二分圖 cover: array1 . maxn of boolean; 標(biāo)記一個(gè)點(diǎn)是否為飽和點(diǎn) link: array1 . maxn of integer; 保存匹配邊 n: integer; 頂點(diǎn)數(shù)procedure init; 讀入var i, e, x, y: integer;begin assign(input, 'inpu

7、t.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出發(fā)，找增廣鏈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; if

8、 (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 := 1

9、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.二分圖的最大權(quán)匹配對(duì)于上面的人員分配問(wèn)題，如果還考慮到工人做工的效率，就可以提出所謂的分派問(wèn)題：應(yīng)該怎樣分配才能使總的效率最大？同上一節(jié)，我們可以構(gòu)造一個(gè)二分圖G，如果把工人xi做工作yi的效率wij看作是G中邊xiyi的權(quán)，則分派問(wèn)題就

10、相當(dāng)于在賦權(quán)二分圖G中求一個(gè)最大全匹配。由線性規(guī)劃的知識(shí)，求二分圖G的最大權(quán)匹配，只需在匈牙利算法的基礎(chǔ)上少許改進(jìn)即可。它的基本思想是，對(duì)二分圖的頂點(diǎn)編號(hào)，然后根據(jù)編號(hào)構(gòu)造一個(gè)新的二分圖G，最后把求G的最大權(quán)匹配轉(zhuǎn)換為求G的完美匹配。下面的這條定理是這個(gè)算法的理論基礎(chǔ)。定理：設(shè)是賦權(quán)圖（權(quán)非負(fù)）的完全二分圖的一個(gè)完美匹配，這里。如果存在一組，滿足，并且對(duì)一切，均有，則是的最大權(quán)匹配。下面，給出求最大權(quán)匹配的程序。輸入文件中首先是N和|E|，下面|E|行每行三個(gè)數(shù)(I, J, W)，表示工人I做工作J的效率是W。程序輸出包括每個(gè)工人的選擇和最后的總效益。其它假設(shè)參見(jiàn)上一節(jié)的算法假設(shè)。這個(gè)算法的時(shí)

11、間復(fù)雜度也是O(n3)。Program maxmatch;const maxn = 100;var map: array1 . maxn, 1 . maxn of integer;保存二分圖 link, lx, ly: array1 . maxn of integer;保存匹配邊和每個(gè)點(diǎn)的標(biāo)號(hào) x, y: array1 . maxn of boolean; 標(biāo)記一個(gè)點(diǎn)是否為飽和點(diǎn) n: integer; 頂點(diǎn)數(shù)procedure init; 讀入var i, e, x, y: integer;begin assign(input, 'input.txt'); reset(inp

12、ut); readln(n, e); for i := 1 to e do readln(x, y, mapx, y); close(input);end;function find(v: integer): boolean;從v出發(fā)，找增廣鏈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) then

13、 exit; linki := k; end; find := false;end;procedure main; 求最大權(quán)匹配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, size

14、of(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; 輸出v

15、ar 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. 任意圖的匹配任意圖的最大匹配算法也是建立在找增廣鏈的基礎(chǔ)上的，只是任意圖的增廣鏈要比二分圖難找得多。這個(gè)算法比較復(fù)雜，競(jìng)賽中也很少用到，因此，這里就不做詳細(xì)介紹了。三、匹配的應(yīng)用1. 匹配與一一對(duì)應(yīng)問(wèn)題：FJOI-信封問(wèn)題J

16、ohn先生晚上寫了n封信，并相應(yīng)地寫了n個(gè)信封將信裝好，準(zhǔn)備寄出。但是，第二天John的兒子Small John將這n封信都拿出了信封。不幸的是，Small John無(wú)法將拿出的信正確地裝回信封中了。將Small John所提供的n封信依次編號(hào)為1，2，n；且n個(gè)信封也依次編號(hào)為1，2，n。假定Small John能提供一組信息：第i封信肯定不是裝在信封j中。請(qǐng)編程幫助Small John，盡可能多地將信正確地裝回信封。其中n100。例如，有4封信，而且第一封信不是裝在信封1、2和3中，第2封信不是裝在信封2和3中，則可以確定的第一封信裝在信封4中，而且第二封信則裝在信封1中。但這些條件還不足

17、以確定第三封和第四封信的位置。分析：看了這道題目，感覺(jué)上和小學(xué)數(shù)學(xué)競(jìng)賽中的邏輯推理題如出一轍，而邏輯推理題的做法一般是表上作業(yè)法。就以前面的例子為例，根據(jù)條件，可以得到如下信息：信封信12341×××2××34表格 1由于每一行每一列都應(yīng)該只有一個(gè)，因此，可以確定第一封信裝在信封4中，于是可以得到：信封信12341×××2×××3×4×表格 2然后，發(fā)現(xiàn)第二行有3個(gè)×,因此剩下一個(gè)肯定是，于是就可以得出第二封信則裝在信封1中：信封信12341×&

18、#215;×2×××3××4××表格 3現(xiàn)在，第3行和第4行都只有兩個(gè)×，因此無(wú)法確定它們放在那個(gè)信封里。這樣我們就得到了一個(gè)初步的算法：在程序中建立一個(gè)二維表格，首先，根據(jù)條件填入若干個(gè)×，然后，檢查所有還未確定的行和列，看有沒(méi)有一行（列）中有n 1個(gè)×，如果沒(méi)有，就結(jié)束；否則，把剩下的那一個(gè)空格填上，并且填了的那一行（列）的其它位置都填上×。這種方法雖然很容易想到，但卻有針對(duì)這個(gè)方法的反例，例如：圖表 3 一個(gè)反例圖中上半部分的頂點(diǎn)表示“信”，下半部分的頂點(diǎn)表示“信封”，

19、如果信i可能放在信封j中，則在信i和信封j之間連一條邊。由于每個(gè)頂點(diǎn)的度數(shù)都大于或等于2，即每行每列都至少有兩個(gè)空位，故前面的算法無(wú)法進(jìn)行任何推理，而事實(shí)卻并非如此，比如說(shuō)中間的那封信就只能放在中間的那個(gè)信封里。正是這個(gè)反例，使我們需要另辟蹊徑。進(jìn)一步分析可以發(fā)現(xiàn)，信和信封之間的關(guān)系，是一種一一對(duì)應(yīng)的關(guān)系，這是因?yàn)橐环庑胖荒芊诺揭粋€(gè)信封里，而一個(gè)信封也只能裝一封信。而從信息學(xué)的角度來(lái)看，這種一一對(duì)應(yīng)的關(guān)系，也可以看作是二分圖的匹配關(guān)系。令X=x1, x2, , xm，Y=y1, y2, ,yn，構(gòu)造二分圖G=(X, Y, E)，當(dāng)且僅當(dāng)信i可以放到信封j中，G中存在邊xiyj。這樣，任何一種信

20、的分配方案，都可以看作是圖G的一個(gè)完美匹配。例如上圖就有且僅有如下兩種完美匹配：圖表 4 所有的完美匹配由于中間的那條匹配邊在兩個(gè)完美匹配中都出現(xiàn)了，因此我們認(rèn)為這條匹配邊是“確定的”，換句話說(shuō)，這條邊所代表的關(guān)系也是確定的。容易看出，當(dāng)且僅當(dāng)對(duì)于G的所有完美匹配M，都存在一條匹配邊xiyj，則可以確定信i可以放到信封j中。這樣，我們就從匹配的角度建立了一個(gè)新的模型。那么，這個(gè)模型要如何求解呢？我們當(dāng)然不能枚舉出G所有的完美匹配，然后再去求它們邊的交集這和搜索就沒(méi)什么分別。在這里，我們需要對(duì)這個(gè)模型再做一個(gè)小小的轉(zhuǎn)換：我們發(fā)現(xiàn)，條件“對(duì)于G的所有完美匹配M，都存在一條匹配邊xiyj”，等價(jià)于“

21、如果圖G存在完美匹配，而刪除圖G中的一條邊xiyj得到的圖G中卻不存在完美匹配”。例如，左下圖刪除了一條“關(guān)鍵邊”，故不存在完美匹配，而右下圖刪除的是一條“非關(guān)鍵邊”，故存在完美匹配。圖表 5 刪邊的例子從表面上看，這個(gè)算法的時(shí)間復(fù)雜度似乎仍然很高。因?yàn)閳DG中最多有n2條邊，每次試著刪除一條邊，又需要O(n3)的時(shí)間復(fù)雜度求一次完美匹配。總的復(fù)雜度高達(dá)O(n5)。實(shí)際上，我們可以先找到圖G的一個(gè)完美匹配M，這樣，刪邊就只需考慮匹配邊了（因?yàn)閯h除非匹配邊得到G，M仍然是G的完美匹配）。這樣，只需刪除n條邊，時(shí)間復(fù)雜度就降到了O(n4)。再進(jìn)一步分析，刪除一條邊以后，沒(méi)有必要重新找完美匹配，只需檢

22、查可不可以找到新的增廣鏈就可以了。這樣，時(shí)間復(fù)雜度就進(jìn)一步降到了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: integer;begi

23、n 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, sizeof(map),

24、 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); if not

25、 path(y) then begin linkx := y; writeln(x, ' ', y); end; mapy, x := true; end; close(output); close(input);end.2.“完美”的最大權(quán)匹配問(wèn)題：CTSC-丘比特的煩惱隨著社會(huì)的不斷發(fā)展，人與人之間的感情越來(lái)越功利化。最近，愛(ài)神丘比特發(fā)現(xiàn)，愛(ài)情也已不再是完全純潔的了。這使得丘比特很是苦惱，他越來(lái)越難找到合適的男女，并向他們射去丘比特之箭。于是丘比特千里迢迢遠(yuǎn)赴中國(guó)，找到了掌管東方人愛(ài)情的神月下老人，向他求教。月下老人告訴丘比特，純潔的愛(ài)情并不是不存在，而是他沒(méi)有找到。在東方

26、，人們講究的是緣分。月下老人只要做一男一女兩個(gè)泥人，在他們之間連上一條紅線，那么它們所代表的人就會(huì)相愛(ài)無(wú)論他們身處何地。而丘比特的愛(ài)情之箭只能射中兩個(gè)距離相當(dāng)近的人，選擇的范圍自然就小了很多，不能找到真正的有緣人。丘比特聽了月下老人的解釋，茅塞頓開，回去之后用了人間的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。這樣，射中有緣人的機(jī)會(huì)也增加了不少。情人節(jié)(Valentine's day)的午夜零時(shí)，丘比特開始了自己的工作。他選擇了一組數(shù)目相等的男女，感應(yīng)到他們互相之間的緣分大小，并依次射出了神箭，使他們產(chǎn)生愛(ài)意。他希望能選擇最好的方法，使被他選擇的每一個(gè)人被射中一次，且每一對(duì)

27、被射中的人之間的緣分的和最大。當(dāng)然，無(wú)論丘比特怎么改造自己的弓箭，總還是存在缺陷的。首先，弓箭的射程盡管增大了，但畢竟還是有限的，不能像月下老人那樣，做到“千里姻緣一線牽”。其次，無(wú)論怎么改造，箭的軌跡終歸只能是一條直線，也就是說(shuō)，如果兩個(gè)人之間的連線段上有別人，那么莫不可向他們射出丘比特之箭，否則，按月下老人的話，就是“亂點(diǎn)鴛鴦譜”了。作為一個(gè)凡人，你的任務(wù)是運(yùn)用先進(jìn)的計(jì)算機(jī)為丘比特找到最佳的方案。輸入文件第一行為正整數(shù)k，表示丘比特之箭的射程，第二行為正整數(shù)n(n<30)，隨后有2n行，表示丘比特選中的人的信息，其中前n行為男子，后n行為女子。每個(gè)人的信息由兩部分組成：他的姓名和他的

28、位置。姓名是長(zhǎng)度小于20且僅包含字母的字符串，忽略大小寫的區(qū)別，位置是由一對(duì)整數(shù)表示的坐標(biāo)，它們之間用空格分隔。格式為Name x y。輸入文件剩下的部分描述了這些人的緣分。每一行的格式為Name1 Name2 p。Name1和Name2為有緣人的姓名，p是他們之間的緣分值(p為小于等于255的正整數(shù))。以一個(gè)End作為文件結(jié)束標(biāo)志。每?jī)蓚€(gè)人之間的緣分至多只被描述一次。如果沒(méi)有被描述，則說(shuō)明他們緣分值為1。輸出文件僅一個(gè)正整數(shù)，表示每一對(duì)被射中的人之間的緣分的總和。這個(gè)和應(yīng)當(dāng)是最大的。分析：題目中出現(xiàn)了三類物體和兩種關(guān)系，我們一個(gè)個(gè)的來(lái)分析：丘比特的箭，它有一個(gè)屬性是射程，男人和女人，他們的屬

29、性包括名字和位置，男人和女人之間的關(guān)系，這個(gè)關(guān)系是他們倆的緣分值，箭與男女的關(guān)系，如果兩人的距離不超過(guò)箭的射程，并無(wú)他人阻擋，則可能被箭射中。題目就是要求一種射箭的方案，使得所有被射中的男女的緣分和最大。這個(gè)問(wèn)題很像是要求一個(gè)二分圖的最大權(quán)匹配。因?yàn)槟腥撕团朔謱賰蓚€(gè)集合，而且同性之間沒(méi)有任何關(guān)系，因此是一個(gè)二分圖。而把緣分值記做邊上的權(quán)，則緣分和最大，就對(duì)應(yīng)了這個(gè)二分圖中的一個(gè)最大權(quán)匹配。要注意的是，題目中雖然說(shuō)明沒(méi)有被描述的男女之間緣分值為1，但這并不代表所得到的二分圖是完全二分圖。因?yàn)樵跇?gòu)圖的過(guò)程中，我們必須還考慮到箭的射程等因素如果兩人的距離超過(guò)了箭的射程，則他倆注定無(wú)緣了。這時(shí)問(wèn)題就

30、來(lái)了，因?yàn)轭}目中除了要求緣分和最大之外，還要求“被丘比特選擇的每一個(gè)人都要被射中一次”。你可能會(huì)覺(jué)得，要緣分和越大，當(dāng)然被射中的人越多越好，其實(shí)并不是這樣。例如：圖表 6 一個(gè)反例如果要求最大權(quán)匹配，則會(huì)選擇匹配邊AD，緣分和為10。但由于每個(gè)人都要被射中一次，因此我們只能選擇AC和BD，緣分和為2。換句話說(shuō)，對(duì)于這個(gè)例子，正確答案應(yīng)該是2，而最大權(quán)匹配的值卻是10。這說(shuō)明，這道題目和簡(jiǎn)單的最大權(quán)匹配還是有區(qū)別的，因?yàn)轭}目再要求權(quán)值最大的同時(shí)，還要求是一個(gè)完美匹配，我們稱之為“完美”的最大權(quán)匹配。那么，這道題是否就不能用最大權(quán)匹配來(lái)做了呢？先別急，我們?cè)賮?lái)回顧一下求最大權(quán)匹配的算法：我們通過(guò)對(duì)

31、頂點(diǎn)編號(hào),將圖G轉(zhuǎn)化為G，然后在把求G的最大權(quán)匹配轉(zhuǎn)換為求G的完美匹配這里好像就是求完美匹配，但對(duì)于上面的那個(gè)例子，又為什么不呢？原來(lái)，對(duì)于上面的例子，在標(biāo)號(hào)過(guò)后，新的圖G中加入了一條新的邊BC，而這條邊的權(quán)值是0，在圖G中的完美匹配，實(shí)際上是AD和BC，對(duì)應(yīng)到圖G中，就是邊AD了。因此，如果我們預(yù)先把BC的邊的權(quán)值設(shè)為，再求圖中的最大權(quán)匹配，就不會(huì)再有問(wèn)題了。更一般的，如果要求二分圖的“完美”的最大權(quán)匹配，只需將原圖中沒(méi)有的邊的權(quán)值設(shè)為，就可以了。下面給出這道題目的程序。program cupid;const finp = 'cupid.in' fout = 'cup

32、id.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 of boolea

33、n;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; 找編號(hào)begin re

34、sult := 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 := linkk;

35、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);end;begi

36、n 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 break; i := p

37、os(' ', 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; va

38、l(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, j := 0;

39、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 := maxint; for i

40、 := 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 + maplin

41、ki, i; writeln(len); close(output); close(input);end.3. 稀疏圖的匹配問(wèn)題：IPSC-Magic一個(gè)著名的魔術(shù)師上臺(tái)表演，跟著他的是一位漂亮的女助手。魔術(shù)師先從他的魔術(shù)帽中拽出了幾只兔子，接著他又從女助手的圍巾中變出了一束鮮花，最后，他把女助手鎖在一個(gè)看上去空著的箱子里。然后，魔術(shù)師選了一個(gè)觀眾來(lái)配合一個(gè)表演：他在一個(gè)桌子上擺出N張牌（所有N張牌兩兩不同，且N為奇數(shù)）。魔術(shù)師讓這位自愿者走上講臺(tái)從中選出（N+1）/2張牌，其余的牌都在魔術(shù)師的帽子里永遠(yuǎn)的消失了。魔術(shù)師在選出的牌上方晃了晃手，接著他選出其中一張交給那一位自愿者，自愿者向觀眾展

42、示了手中的這張牌，隨后又將其藏在自己的衣袋里。那位女助手從箱子里放出來(lái)后，來(lái)到桌前也在剩下的（N1）21張牌上方晃了晃手，馬上就說(shuō)出了自愿者衣袋中的是什么牌。這是為什么呢？我們先看一下下面這張表，這是N=5的情況：自愿者選的牌魔術(shù)師選的牌助手所看到的牌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其中，自愿者選的牌魔術(shù)師選的牌助手所看到的牌。表中包括了自愿者選牌的所有可能性，它們兩兩不同。而助手所看到的牌，也是兩兩不同的。首先，魔術(shù)師和他的助手都要記住這

43、張表。這樣，當(dāng)助手看到的牌是2，4時(shí)，她就可以肯定自愿者選的牌是2，4，5，且魔術(shù)師選的牌就是5?，F(xiàn)在，告訴你n的值，要你求出這張表。其中n15。分析：為了便于分析，我們令M表示從N張牌中選?。∟1）2張牌的方案數(shù)，顯然，從這N張牌中選出（N1）21張牌的方案數(shù)也是M。我們先從枚舉的角度入手，下面給出兩種枚舉的方法：對(duì)于自愿者的每種選牌的方案，枚舉魔術(shù)師所選的牌。對(duì)于自愿者的每種選牌的方案，所對(duì)應(yīng)的助手看到的牌。方案一需要M次決策，每次決策中有N種選擇；方案二同樣需要M次決策，而每次決策的可以有M種選擇。從這點(diǎn)上來(lái)看，方案一要好得多。、可是方案一所表現(xiàn)出來(lái)的“自愿者的選牌的方案”和“魔術(shù)師所選

44、的牌”之間的關(guān)系并不是一一對(duì)應(yīng)的關(guān)系，對(duì)于自愿者不同的選牌的方案，魔術(shù)師可以選擇相同的牌。而方案二中所表現(xiàn)出的關(guān)系正是一一對(duì)應(yīng)的關(guān)系，因?yàn)轭}目要求對(duì)于自愿者不同的選牌的方案，助手看到的牌必須不同。前面已經(jīng)提到過(guò)，從信息學(xué)的角度來(lái)看，一一對(duì)應(yīng)，也可以看作是一種二分圖的匹配的關(guān)系。因此，方案二更容易讓人聯(lián)系到匹配。令X=自愿者的選牌的方案集，Y=助手看到的牌的集合，構(gòu)造二分圖G=(X, Y, E)，當(dāng)且僅當(dāng)時(shí)，G中存在邊xiyj。這樣，就把原問(wèn)題轉(zhuǎn)換成求圖G的一個(gè)完美匹配。下面問(wèn)題又來(lái)了。首先，二分圖的頂點(diǎn)高達(dá)2M個(gè)，當(dāng)N=15時(shí)，M接近8000，而求匹配的復(fù)雜度為O(M3)，這樣高的復(fù)雜度，如何

45、能夠承受？注意到這個(gè)圖是一個(gè)稀疏圖，一共只有MN條邊。而稀疏二分圖匹配的復(fù)雜度也可以表示成O(|V|×|E|)。因此，時(shí)間復(fù)雜度應(yīng)該是O(M2N)，基本上可以承受了。另外，由于這是稀疏圖，我們用鄰接表來(lái)存儲(chǔ)，則空間復(fù)雜度僅為O(NM)，同樣可以承受。最后要說(shuō)明的是，這道題目也可以用構(gòu)造法以獲得更好的效率，但不如匹配容易想到。具體的構(gòu)造方法這里就不給出了，讀者可以自己想一想。下面給出參考程序：program magic;const n = 15; half = (n + 1) shr 1; m = 8000;var map: array1 . m, 0 . half of intege

46、r; 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 do buildA

47、(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 buildB(d

48、+ 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;procedure

49、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 do show(

50、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(output); su

51、m := 0; show(1, 0, 0); close(output);end.4. 最小最大匹配問(wèn)題：OOPC-神秘之山M個(gè)人在追一只奇怪的小動(dòng)物。眼看就要追到了，那小東西卻一溜煙躥上一座神秘的山。眾人抬頭望去那山看起來(lái)就是這個(gè)樣子：圖表 7 樣例示意圖那山由N1條線段組成。各個(gè)端點(diǎn)從左到右編號(hào)為0N1，即xi<xi1(0in)。而且有y0=yn1=0。根據(jù)經(jīng)驗(yàn)來(lái)說(shuō)那小東西極有可能藏在1N 中的某個(gè)端點(diǎn)。有趣的是大家很快發(fā)現(xiàn)了原來(lái)M恰好等于N，這樣，他們決定每人選一個(gè)點(diǎn)，看看它是否在躲那里。一開始，他們都在山腳下，第i 個(gè)人的位置是（si, 0）。他們每人選擇一個(gè)中間點(diǎn)（xi, 0）

52、，先以速度wi水平走到那里，再一口氣沿直線以速度ci爬到他的目的地。由于他們的數(shù)學(xué)不好，他們只知道如何選擇一個(gè)最好的整數(shù)來(lái)作為中間點(diǎn)的橫坐標(biāo)xi。而且很明顯，路線的任何一個(gè)部分都不能在山的上方（他們又不會(huì)飛）。他們不希望這次再失敗了，因此隊(duì)長(zhǎng)決定要尋找一個(gè)方案，使得最后一個(gè)到達(dá)目的地的人盡量早點(diǎn)到。他們?cè)撛趺醋瞿兀科渲?N100，0xi, yi, si1000，1ci<wi100。輸入第一行包含一個(gè)整數(shù)N。以下N+2行每行，包含兩個(gè)整數(shù)xi和yi，代表相應(yīng)端點(diǎn)的坐標(biāo)。以下N行每行包含3個(gè)整數(shù)：ci,wi和si，代表第i個(gè)人的爬山速度，行走速度和初始位置輸出輸出最后一個(gè)人到達(dá)目的地的最早可

53、能時(shí)間，四舍五入到小數(shù)點(diǎn)后兩位。樣例輸入30 03 46 112 616 02 4 48 10 154 25 14樣例輸出1.43樣例說(shuō)明在這里例子中，第一個(gè)人先到（5,0）再爬到端點(diǎn)2；第二個(gè)人直接爬到端點(diǎn)3；第三個(gè)人先到（4, 0）再爬到端點(diǎn)1。如下圖：圖表 8 樣例的解答分析：題目中的數(shù)據(jù)繁多復(fù)雜，我們先把他們提出來(lái)一個(gè)個(gè)分析：人，共n個(gè)，與之有關(guān)的有初始橫坐標(biāo)s，速度w和c山頭，共n個(gè)，與之有關(guān)的有坐標(biāo)x和y根據(jù)這些信息，可以得到，人和山頭的關(guān)系：tI, J，表示第i個(gè)人到達(dá)山頭j所需的最短時(shí)間。題目中已經(jīng)指明是一個(gè)人負(fù)責(zé)一個(gè)山頭，這顯然是一個(gè)一一對(duì)應(yīng)的關(guān)系，因此，我們可以從二分圖的匹配的角度來(lái)考慮這個(gè)問(wèn)題。那么，這道題目屬于哪一種匹配呢？是簡(jiǎn)單的最大匹配，還是最大權(quán)匹