第5-4節(jié) 圖的匹配

1、第四節(jié) 圖的匹配頁： 圖表的標(biāo)號，程序的注釋一、什么是圖的匹配1.圖的定義無向圖：無向圖G是指非空有限集合VG，和VG中某些元素的無序?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)成的無序?qū)?vi，vj)相對應(yīng)，記evivj，或evjvi。在分析問題時(shí)，我們通常可以用小圓圈表示頂點(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的最大匹配。對于圖G(V，E)，在每條邊e上賦一個(gè)實(shí)數(shù)權(quán)w(e)。設(shè)M是G的一個(gè)匹配。定義，并稱之為匹配M的權(quán)。G中權(quán)最大的匹配稱為G的最大權(quán)匹配。如果對一切，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增廣鏈。二、匹配算法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)工作。問應(yīng)怎樣分配才能使盡可能多的工人分配到他勝任的工作。這個(gè)問題稱為人員分配問題。人員分配問題可以用圖的語言來表述。令X=x1, x2, , xm，Y=y1, y2, ,yn，構(gòu)造二分圖G=(X, Y, E)如下：對于1im，1jn，當(dāng)且僅當(dāng)工人xi勝任工作yi時(shí)，G中有一條邊xiyi，于是人員分配問題就成為在G中求一個(gè)最大匹配的問題。求最大匹配常用匈牙利算法，它的基本思想是：對于已知的匹配M，從X中的任一選定的M非飽和點(diǎn)出發(fā)，用標(biāo)號法尋找M增廣鏈。如果找到M增廣鏈，則M就可以得到增廣；否則從X中另一個(gè)M非飽和點(diǎn)出發(fā)，繼續(xù)尋找M增廣鏈。重復(fù)這個(gè)過程直到

5、G中不存在增廣鏈結(jié)束，此時(shí)的匹配就是G的最大匹配。這個(gè)算法通常稱為匈牙利算法，因?yàn)檫@里介紹的尋找增廣鏈的標(biāo)號方法是由匈牙科學(xué)者Egerváry最早提出來的。圖表 2 匈牙利算法理解了這個(gè)算法，就不難寫出人員分配問題的解答了。在給出程序之前，先做一些假設(shè)：為了簡單起見，假設(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。下面是人員分配問題的參考解答，該算法的時(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, '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出發(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;

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

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

11、的時(shí)間復(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)號 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

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出發(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)

13、 then 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,

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

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

17、條件還不足以確定第三封和第四封信的位置。分析：看了這道題目，感覺上和小學(xué)數(shù)學(xué)競賽中的邏輯推理題如出一轍，而邏輯推理題的做法一般是表上作業(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è)×，因此無法確定它們放在那個(gè)信封里。這樣我們就得到了一個(gè)初步的算法：在程序中建立一個(gè)二維表格，首先，根據(jù)條件填入若干個(gè)×，然后，檢查所有還未確定的行和列，看有沒有一行（列）中有n 1個(gè)×，如果沒有，就結(jié)束；否則，把剩下的那一個(gè)空格填上，并且填了的那一行（列）的其它位置都填上×。這種方法雖然很容易想到，但卻有針對這個(gè)方法的反例，例如：圖表 3 一個(gè)反例圖中上半部分的頂點(diǎn)表示“信”，下半部分的頂點(diǎn)表示

19、“信封”，如果信i可能放在信封j中，則在信i和信封j之間連一條邊。由于每個(gè)頂點(diǎn)的度數(shù)都大于或等于2，即每行每列都至少有兩個(gè)空位，故前面的算法無法進(jìn)行任何推理，而事實(shí)卻并非如此，比如說中間的那封信就只能放在中間的那個(gè)信封里。正是這個(gè)反例，使我們需要另辟蹊徑。進(jìn)一步分析可以發(fā)現(xiàn)，信和信封之間的關(guān)系，是一種一一對應(yīng)的關(guān)系，這是因?yàn)橐环庑胖荒芊诺揭粋€(gè)信封里，而一個(gè)信封也只能裝一封信。而從信息學(xué)的角度來看，這種一一對應(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)為這條匹配邊是“確定的”，換句話說，這條邊所代表的關(guān)系也是確定的。容易看出，當(dāng)且僅當(dāng)對于G的所有完美匹配M，都存在一條匹配邊xiyj，則可以確定信i可以放到信封j中。這樣，我們就從匹配的角度建立了一個(gè)新的模型。那么，這個(gè)模型要如何求解呢？我們當(dāng)然不能枚舉出G所有的完美匹配，然后再去求它們邊的交集這和搜索就沒什么分別。在這里，我們需要對這個(gè)模型再做一個(gè)小小的轉(zhuǎn)換：我們發(fā)現(xiàn)，條件“對于G的所有完美匹配M，都存在一條匹配邊xiyj

21、”，等價(jià)于“如果圖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)一步分析，刪除一條邊以后，沒有必要重新找完

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: 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. “完美”的最大權(quán)匹配問題：CTSC-丘比特的煩惱隨著社會的不斷發(fā)展，人與人之間的感情越來越功利化。最近，愛神丘比特發(fā)現(xiàn)，愛情也已不再是完全純潔的了。這使得丘比特很是苦惱，他越來越難找到合適的男女，并向他們射去丘比特之箭。于是丘比特千里迢迢遠(yuǎn)赴中國，找到了掌管東方人愛情的神月下老人，向他求教。月下老人告訴丘比特，純潔的愛情并不是不存在，而是他

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

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

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

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

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

31、算法：我們通過對頂點(diǎn)編號, 將圖G轉(zhuǎn)化為G，然后在把求G的最大權(quán)匹配轉(zhuǎn)換為求G的完美匹配這里好像就是求完美匹配，但對于上面的那個(gè)例子，又為什么不呢？原來，對于上面的例子，在標(biāo)號過后，新的圖G中加入了一條新的邊BC，而這條邊的權(quán)值是0，在圖G中的完美匹配，實(shí)際上是AD和BC，對應(yīng)到圖G中，就是邊AD了。因此，如果我們預(yù)先把BC的邊的權(quán)值設(shè)為，再求圖中的最大權(quán)匹配，就不會再有問題了。更一般的，如果要求二分圖的“完美”的最大權(quán)匹配，只需將原圖中沒有的邊的權(quán)值設(shè)為，就可以了。下面給出這道題目的程序。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一個(gè)著名的魔術(shù)師上臺表演，跟著他的是一位漂亮的女助手。魔術(shù)師先從他的魔術(shù)帽中拽出了幾只兔子，接著他又從女助手的圍巾中變出了一束鮮花，最后，他把女助手鎖在一個(gè)看上去空著的箱子里。然后，魔術(shù)師選了一個(gè)觀眾來配合一個(gè)表演：他在一個(gè)桌子上擺出N張牌（所有N張牌兩兩不同，且N為奇數(shù)）。魔術(shù)師讓這位自愿者走上講臺從中選出（N+1）/2張牌，其余的牌都在魔術(shù)師的帽子里永遠(yuǎn)的消失了。魔術(shù)師在選出的牌上方晃了晃手，接著他選出其中一張交給那一位自愿

42、者，自愿者向觀眾展示了手中的這張牌，隨后又將其藏在自己的衣袋里。那位女助手從箱子里放出來后，來到桌前也在剩下的（N1）21張牌上方晃了晃手，馬上就說出了自愿者衣袋中的是什么牌。這是為什么呢？我們先看一下下面這張表，這是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。現(xiàn)在，告訴你n的值，要你求出這張表。其中n15。分析：為了便于分析，我們令M表示從N張牌中選?。∟1）2張牌的方案數(shù)，顯然，從這N張牌中選出（N1）21張牌的方案數(shù)也是M。我們先從枚舉的角度入手，下面給出兩種枚舉的方法：對于自愿者的每種選牌的方案，枚舉魔術(shù)師所選的牌。對于自愿者的每種選牌的方案，所對應(yīng)的助手看到的牌。方案一需要M次決策，每次決策中有N種選擇；方案二同樣需要M次決策，而每次決策的可以有M種選擇。從這點(diǎn)上來看，方案一要好得多。、可是方案一所表現(xiàn)出來的“自愿者的選牌的方

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

45、樣高的復(fù)雜度，如何能夠承受？注意到這個(gè)圖是一個(gè)稀疏圖，一共只有MN條邊。而稀疏二分圖匹配的復(fù)雜度也可以表示成O(|V|×|E|)。因此，時(shí)間復(fù)雜度應(yīng)該是O(M2N)，基本上可以承受了。另外，由于這是稀疏圖，我們用鄰接表來存儲，則空間復(fù)雜度僅為O(NM)，同樣可以承受。最后要說明的是，這道題目也可以用構(gòu)造法以獲得更好的效率，但不如匹配容易想到。具體的構(gòu)造方法這里就不給出了，讀者可以自己想一想。下面給出參考程序：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個(gè)人在追一只奇怪的小動物。眼看就要追到了，那小東西卻一溜煙躥上一座神秘的山。眾人抬頭望去那山看起來就是這個(gè)樣子：圖表 7 樣例示意圖那山由N1條線段組成。各個(gè)端點(diǎn)從左到右編號為0N1，即xi<xi1(0in)。而且有y0=yn1=0。根據(jù)經(jīng)驗(yàn)來說那小東西極有可能藏在1N 中的某個(gè)端點(diǎn)。有趣的是大家很快發(fā)現(xiàn)了原來M恰好等于N，這樣，他們決定每人選一個(gè)點(diǎn)，看看它是否在躲那里。一開始，他們都在山腳下，第i 個(gè)人的位置是（si, 0）。他們每人選擇一個(gè)中

52、間點(diǎn)（xi, 0），先以速度wi水平走到那里，再一口氣沿直線以速度ci爬到他的目的地。由于他們的數(shù)學(xué)不好，他們只知道如何選擇一個(gè)最好的整數(shù)來作為中間點(diǎn)的橫坐標(biāo)xi。而且很明顯，路線的任何一個(gè)部分都不能在山的上方（他們又不會飛）。他們不希望這次再失敗了，因此隊(duì)長決定要尋找一個(gè)方案，使得最后一個(gè)到達(dá)目的地的人盡量早點(diǎn)到。他們該怎么做呢？其中1N100，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è)

53、人到達(dá)目的地的最早可能時(shí)間，四舍五入到小數(shù)點(diǎn)后兩位。樣例輸入30 03 46 112 616 02 4 48 10 154 25 14樣例輸出1.43樣例說明在這里例子中，第一個(gè)人先到（5, 0）再爬到端點(diǎn)2；第二個(gè)人直接爬到端點(diǎn)3；第三個(gè)人先到（4, 0）再爬到端點(diǎn)1。如下圖：圖表 8 樣例的解答分析：題目中的數(shù)據(jù)繁多復(fù)雜，我們先把他們提出來一個(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è)一一對應(yīng)的關(guān)系，因此，我們可以從二分圖的匹配的角度來考慮這個(gè)問題。那么，這道題目屬于哪一種匹配呢？是簡單的