二分圖及二分圖匹配及并查集

1、二分圖及其二分圖的匹配如果可以以某一種方式將題目中的對(duì)象分成兩個(gè)互補(bǔ)的集合，而需要求得他們之間滿足某種條件的“一一對(duì)應(yīng)”關(guān)系時(shí)，往往可以抽象出對(duì)象以及對(duì)象之間的關(guān)系，構(gòu)造二分圖，然后利用匹配算法來解決。這類題目通常需要考察選手構(gòu)建二分圖模型、設(shè)計(jì)匹配算法、并對(duì)其算法進(jìn)行適當(dāng)優(yōu)化等方面的能力。通過DFS判別二分圖二分圖分成兩個(gè)頂點(diǎn)子集X和Y。若頂點(diǎn)i屬于集合X，則相鄰點(diǎn)j必屬于集合Y。 proc dfs(d,集合標(biāo)志); /*從d置入某集合的初始狀態(tài)出發(fā)，判別二分圖*/定義d的相鄰點(diǎn)u的數(shù)據(jù)類型; if 非二分圖標(biāo)志 then exit；if d已屬于本集合 then exit；if d屬于另一

2、集合 then 失敗退出;設(shè)d的本集合標(biāo)志;取d的第1個(gè)相鄰點(diǎn)u；while u存在 do dfs(u,另一集合標(biāo)志)； ud的下一個(gè)相鄰點(diǎn);/* dfs */依次搜索每個(gè)無集合標(biāo)志的頂點(diǎn)i，執(zhí)行dfs(i,X集合標(biāo)志)。最后未失敗退出的情況，則說明圖為二分圖。*例題：雙棧排序【問題描述】Tom最近在研究一個(gè)由趣的排序問題。如圖所示，通過2個(gè)棧S1和S2，Tom希望借助以下4種操作實(shí)現(xiàn)將輸入序列升序排序。操作a：如果輸入序列不為空，將第一個(gè)元素壓入棧S1操作b：如果棧S1不為空，將S1棧頂元素彈出至輸出序列操作c：如果輸入序列不為空，將第一個(gè)元素壓入棧S2操作d：如果棧S2不為空，將S2棧頂元

3、素彈出至輸出序列如果一個(gè)1n的排列P可以通過一系列操作使得輸出序列為1,2，（n-1），n，Tom就稱為P是一個(gè)“可雙棧排序序列”。例如（1,3,2,4）就是一個(gè)“可雙棧排序序列”，而（2,3,4,1）不是。下圖描述了一個(gè)將（1,3,2,4）排序的操作序列：。當(dāng)然，這樣的操作序列有可能有幾個(gè)，對(duì)于上例（1,3,2,4），是另外一個(gè)可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么?【輸入】輸入文件twostach.in的第一行是一個(gè)整數(shù)n。第二行有n個(gè)用空格隔開的正整數(shù)，構(gòu)成一個(gè)1n的排列?！据敵觥枯敵鑫募wostack.out共一行，如果輸入的排列不是“可雙棧排序排列”，輸出數(shù)字

4、0；否則輸出字典序最小的操作序列，每?jī)蓚€(gè)操作之間用空格隔開，行尾沒有空格。簡(jiǎn)述題意有兩個(gè)隊(duì)列和兩個(gè)棧,分別命名為隊(duì)列1(q1),隊(duì)列2(q2),棧1(s1)和棧2(s2)。最初的時(shí)候,q2,s1和s2都為空,而q1中有n個(gè)數(shù)(n1000),為1n的某個(gè)排列.現(xiàn)在支持如下四種操作:a操作,將 q1的首元素提取出并加入s1的棧頂；b操作,將s1的棧頂元素彈出并加入q2的隊(duì)列尾；c操作,將 q1的首元素提取出并加入s2的棧頂；d操作,將s2的棧頂元素彈出并加入q2的隊(duì)列尾；請(qǐng)判斷,是否可以經(jīng)過一系列操作之后,使得q2中依次存儲(chǔ)著1,2,3,n.如果可以,求出字典序最小的一個(gè)操作序列.定理：考慮對(duì)于任

5、意兩個(gè)數(shù)qi和qj,它們不能壓入同一個(gè)棧中的充要條件: 存在一個(gè)k,使得ijk且qkqiqi,這顯然是不正確的.必要性證明：如果兩個(gè)數(shù)不可以壓入同一個(gè)棧,那么它們一定滿足上述條件。證明逆否命題：也就是如果不滿足上述條件,那么這兩個(gè)數(shù)一定可以壓入同一個(gè)棧. 不滿足上述條件有兩種情況:情況1：對(duì)于任意ijk且qiqi;有兩種可能：qkqj或者qkqj時(shí):qi入棧出棧，qj入棧出棧，qk入棧出棧2、qkqj :qi入棧出棧， qj入棧, qk入棧, qk 出棧, qj 出棧結(jié)論：若在qk被壓入棧前,qi已經(jīng)被彈出棧，則qk不會(huì)對(duì)qj產(chǎn)生任何影響。情況2：對(duì)于任意iqj.qi入棧，qj入棧， qj出棧

6、，qi出棧這樣,原命題的逆否命題得證,所以原命題得證。由此得出有解的判斷方法：對(duì)所有的數(shù)對(duì)(i,j)滿足1ijn,檢查是否存在ijk滿足qkqi。1、判斷是否有解和任意兩個(gè)數(shù)能否壓入同一個(gè)棧、對(duì)任意兩個(gè)數(shù)qi和qj,若存在一個(gè)k,使得ijk且qkqiqj，則這兩個(gè)數(shù)分別入s1棧和s2棧、將s1棧和s2棧中的數(shù)字組合成兩個(gè)頂點(diǎn)子集，同一頂點(diǎn)子集內(nèi)不會(huì)出現(xiàn)任何連邊,即不能壓入同一個(gè)棧的所有數(shù)字被分到了兩個(gè)棧中。任兩個(gè)不在同一棧的數(shù)字間連邊。此時(shí)我們只考慮檢查是否有解,所以只要化O(n)時(shí)間檢查這個(gè)圖是不是二分圖,就可以得知是否有解了。找字典序最小的解1、確定每個(gè)數(shù)字入哪個(gè)棧，即構(gòu)造二分圖把二分圖染

7、成1和2兩種顏色,染色為1的結(jié)點(diǎn)被壓入s1棧, 染色為2結(jié)點(diǎn)被壓入s2棧。為了字典序盡量小,我們希望讓編號(hào)小的結(jié)點(diǎn)優(yōu)先壓入s1棧。由于二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取一個(gè)未染色的編號(hào)最小的結(jié)點(diǎn),將它染色為1，并從它開始DFS染色,直到所有結(jié)點(diǎn)都被染色為止。這樣,我們就得到了每個(gè)結(jié)點(diǎn)應(yīng)該壓入哪個(gè)棧中。2、從數(shù)字1開始，按照目標(biāo)序列的遞增順序構(gòu)造操作序列先處理入棧：按照搜索遞增順序每個(gè)頂點(diǎn)：若頂點(diǎn)i的顏色為1，則進(jìn)行a操作，q1i入s1棧；若頂點(diǎn)i的顏色為2，則進(jìn)行c操作，q1i入s2棧。后處理出棧：若s1棧的棧頂元素為目標(biāo)序列的當(dāng)前數(shù)字k，則進(jìn)行b操作，數(shù)字k出s1棧

8、；若s2棧的棧頂元素為目標(biāo)序列的當(dāng)前數(shù)字k，則進(jìn)行d操作，數(shù)字k出s2棧。然后k+1,繼續(xù)模擬，直至k為n為止。數(shù)據(jù)結(jié)構(gòu)vara,b,head,next,point,color:array0.2001of longint; /*初始序列為a（對(duì)應(yīng)q1），后綴的最小值序列為b，其中bi= min a k ；鄰接表的表首頂點(diǎn)為head，后繼指針為next，ikn頂點(diǎn)序列為point，頂點(diǎn)的涂色序列為color*/s:array1.2,0.1000of longint; /*s1棧，棧首指針為s1,0;s2棧, 棧首指針為s2,0*/ n,p,i,j,last:longint; /*序列長(zhǎng)度為n，當(dāng)

9、前應(yīng)取數(shù)字為last*/proc bad ; /*輸出失敗信息*/ writeln(0);close(output);halt /* bad */proc addedge(a,b:longint); /*（a,b）進(jìn)入鄰接表*/var t:longint; inc(p);pointpb; /*增加頂點(diǎn)b*/if heada=0 /*（a,b）進(jìn)入鄰接表*/then headapelse theada;while nextt0 do tnextt;nexttp ;/*else*/;/* addedge */頂點(diǎn)涂色proc dfs(now:longint);var t:longint;thead

10、now; /*搜索與頂點(diǎn)now相鄰的所有頂點(diǎn)*/while t0 do if colorpointt=0 /*若頂點(diǎn)now相鄰的頂點(diǎn)pointt未涂色，則該頂點(diǎn)涂互補(bǔ)色，沿該頂點(diǎn)遞歸下去*/then colorpointt3-colornow;dfs(pointt);/*then*/if colorpointt=colornow /*若頂點(diǎn)now與相鄰頂點(diǎn)pointt涂相同色，則失敗退出*/ then bad;tnextt; /*訪問與頂點(diǎn)now相鄰的下一個(gè)頂點(diǎn)*/;/*while*/;/*dfs*/構(gòu)造二分圖 assign(input,twostack.in);reset(input); /

11、*輸入文件讀準(zhǔn)備*/assign(output,twostack.out);rewrite(output); /*輸出文件寫準(zhǔn)備*/fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0); /*兩?？?/readln(n); /*讀入排列*/for i1 to n do read(ai);bn+1maxlongint;p0;for in downto 1 do /*計(jì)算bi= min a k */ ikn bibi+1;if aibi then biai;/*for*/for i1 to n dofor ji+1 to n doif (bj+1ai)an

12、d(aiaj) /*若ai和aj不能不能壓入同一個(gè)棧，則(i,j)和(j,i)進(jìn)入鄰接表*/then addedge(i,j);addedge(j,i);/*then*/for i1 to n do /*所有未涂色的頂點(diǎn)涂顏色1，遞歸*/ if colori=0 then colori1;dfs(i);/*then*/構(gòu)造操作序列l(wèi)ast1; /*目標(biāo)序列初始化*/for i1 to n do /*模擬輸出序列*/ if colori=1 /*ai入s1或s2棧*/then write(a )else write(c );inc(scolori,0);scolori,scolori,0ai;w

13、hile (s1,s1,0=last) or (s2,s2,0=last) do /*將s1或s2棧頂?shù)臄?shù)字last取出*/ if s1,s1,0=last /*將s1棧頂?shù)膌ast取出*/then write(b );dec(s1,0); /*then*/if s2,s2,0=last /*將s2棧頂?shù)膌ast取出*/then write(d );dec(s2,0); /*then*/inc(last); /*按遞增要求取下一個(gè)數(shù)字*/; /*while*/;/*for*/close(input);close(output);/*關(guān)閉輸入輸出文件*/. /*main*/關(guān)押罪犯S城現(xiàn)有兩座監(jiān)

14、獄，一共關(guān)押著 N名罪犯，編號(hào)分別為 1N。他們之間的關(guān)系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時(shí)可能爆發(fā)沖突。我們用“怨氣值”（一個(gè)正整數(shù)值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為 c 的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會(huì)發(fā)生摩擦，并造成影響力為 c 的沖突事件。每年年末，*局會(huì)將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個(gè)列表，然后上報(bào)到 S 城 Z 市長(zhǎng)那里。公務(wù)繁忙的 Z 市長(zhǎng)只會(huì)去看列表中的第一個(gè)事件的影響力，如果影響很壞，他就會(huì)考慮撤換*局長(zhǎng)。在詳細(xì)考察了 N 名罪犯間的矛盾關(guān)系后，*局長(zhǎng)覺得壓力巨大。

15、他準(zhǔn)備將罪犯?jìng)冊(cè)趦勺O(jiān)獄內(nèi)重新分配，以求產(chǎn)生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個(gè)罪犯間有仇恨，那么他們一定會(huì)在每年的某個(gè)時(shí)候發(fā)生摩擦。那么，應(yīng)如何分配罪犯，才能使 Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力最小？這個(gè)最小值是多少？【輸入】 輸入文件名為 prison.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。 第一行為兩個(gè)正整數(shù) N和 M，分別表示罪犯的數(shù)目以及存在仇恨的罪犯對(duì)數(shù)。 接下來的 M行每行為三個(gè)正整數(shù) aj，bj，cj，表示 aj號(hào)和 bj號(hào)罪犯之間存在仇恨，其怨氣值為 cj。數(shù)據(jù)保證1aj bj N ，0cj 1,000,000,000，且每

16、對(duì)罪犯組合只出現(xiàn)一次?！据敵觥枯敵鑫募?prison.out 共1 行，為 Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力。如果本年內(nèi)監(jiān)獄中未發(fā)生任何沖突事件，請(qǐng)輸出 0。【數(shù)據(jù)范圍】對(duì)于 30%的數(shù)據(jù)有 N15；對(duì)于 70%的數(shù)據(jù)有 N2000，M50000；對(duì)于 100%的數(shù)據(jù)有 N20000，M100000。第一種方法：思維方向1、能否在同所監(jiān)獄的最大怨氣值不超過c的前提下，將所有罪犯分配在兩所監(jiān)獄。定義圖的頂點(diǎn)為罪犯，所有怨氣值大于c的罪犯對(duì)之間連邊，邊權(quán)為怨氣值（連邊的兩個(gè)罪犯不在同一監(jiān)獄）。如果該圖是一個(gè)二分圖，則頂點(diǎn)集合X和Y的罪犯各分配一個(gè)監(jiān)獄，每個(gè)監(jiān)獄的最大怨氣值為c。2、頂點(diǎn)（罪犯）數(shù)

17、的上限為20000，邊權(quán)（怨氣值）的數(shù)據(jù)類型為4個(gè)字節(jié)的longint，因此不能采用圖的相鄰矩陣，只能采用指針類型的鄰接表存儲(chǔ)二分圖，采用邊表存儲(chǔ)原圖。3、按照怨氣值遞增的順序排序罪犯對(duì)。通過二分搜索的辦法尋找同一監(jiān)獄中罪犯對(duì)間最小的最大怨氣值：算法：二分+判定1、給定一個(gè)邊權(quán)值的順序值ans，通過二分圖判斷同一監(jiān)獄中罪犯對(duì)的最大怨氣值是 5否不超過ans按照邊權(quán)遞增的順序排序邊集e定義圖的頂點(diǎn)為罪犯，存在仇恨的罪犯之間連邊，邊權(quán)為怨氣值。將邊eansem加入新圖中，即這些邊的權(quán)值不小于第ans大的權(quán)值采用dfs或者bfs判定新圖是否為一個(gè)二分圖。若是，則表示新圖中任何邊(x,y)的端點(diǎn)x和y

18、不能在同一個(gè)集合中，同一集合（同一監(jiān)獄）中罪犯的最大怨氣值為eans-1的邊權(quán)2、枚舉邊權(quán)的大小順序ans,再通過判定新圖是否為二分圖來判斷能否把罪犯分成兩個(gè)集合，使得同一集合內(nèi)罪犯的怨氣值不超過第ans大。由于ans是滿足單調(diào)性的，如果ans可行，則最小的最大怨氣值在其左區(qū)間，否則最小的最大怨氣值在其右區(qū)間。所以可以通過二分法來枚舉ans。時(shí)間復(fù)雜度：二分復(fù)雜度為O(log(maxci),約為30，判定復(fù)雜度為O(m)，故總復(fù)雜度為O(log(maxci)*m)。(二分復(fù)雜度可以通過離散化進(jìn)一步降為O(log(n),總復(fù)雜度降為O(log(n)*m)數(shù)據(jù)結(jié)構(gòu)Typerectype=recor

19、d/*存在仇恨的罪犯序號(hào)為x、y，怨氣值為c*/x,y,c:longint;end;plink=point;/*單鏈表的指針類型*/point=recordx:longint;next:plink;end; 0頂點(diǎn)i未確定集合var 1頂點(diǎn)i屬于x集合 t:array 1.50000 of plink;/*二分圖的鄰接表*/ 1頂點(diǎn)i屬于y集合 c:array1.50000 of longint;/*頂點(diǎn)i的集合標(biāo)志，ci= - */ e:array 0.200000 of rectype;/*邊表，存儲(chǔ)存在仇恨的罪犯序列*/n,m:longint; /* 罪犯數(shù)為n，存在仇恨的罪犯對(duì)數(shù)為m*

20、/h:boolean; /*二分圖標(biāo)志*/按照怨氣指遞增的順序排列存在仇恨的罪犯對(duì)序列eproc sort(l,r:longint);vari,j,v:longint;temp:rectype; il;jr;ve(l+r) div 2.c;repeatwhile ei.cv do dec(j);if ij;if lj then sort(l,j);if ir then sort(i,r);/* sort */proc init;/* 輸入信息，按照怨氣值遞增的順序排列存在仇恨的罪犯對(duì)序列*/var i:longint; readln(n,m);/*讀罪犯數(shù)和存在仇恨的罪犯對(duì)數(shù)*/for i1

21、to m do readln(ei.x,ei.y,ei.c);/*讀每一對(duì)存在仇恨的罪犯序號(hào)和怨氣值*/ e0.c0;/*虛擬第0對(duì)罪犯的怨氣值為0*/sort(0,m); /*按照怨氣值遞增的順序排列存在仇恨的罪犯對(duì)序列e*/;/* init */proc pro(d,r:longint); /*從r集合中的頂點(diǎn)d出發(fā)，判別二分圖*/var u:plink; if h=false then exit;/*若當(dāng)前圖非二分圖，則回溯*/if cd=r then exit;/*若頂點(diǎn)d已屬于集合r，則回溯*/if cd=-r then hfalse;exit ;/*若頂點(diǎn)d已屬于集合-r，則說明同

22、一集合內(nèi)的頂點(diǎn)間出現(xiàn)邊，返回失敗信息*/cdr;utd;/*頂點(diǎn)d設(shè)r集合標(biāo)志，并繼續(xù)遞歸下去*/while unil do pro(u.x,-r); uu.next;/* pro */判別第min對(duì)罪犯的怨氣值是否在同一集合中最大func check(min:longint):boolean;vari:longint;u:plink; for i1 to n do tinil;/*新圖初始化為空*/for imin to m do /*將大于等于第min對(duì)罪犯的怨氣值的罪犯對(duì)間連邊，構(gòu)造新圖*/ new(u);u.xei.y; u.nexttei.x; tei.xu;new(u);u.xei

23、.x;u.nexttei.y; tei.yu;/*for*/htrue; /*二分圖標(biāo)志初始化*/fillchar(c,sizeof(c),0);/*頂點(diǎn)的集合標(biāo)志初始化*/for i1 to n do/*從每個(gè)未確定集合的頂點(diǎn)出發(fā)，判斷當(dāng)前圖是否二分圖*/ if ci=0 then pro(i,1);if h=false then break ;/*若當(dāng)前圖非二分圖，則失敗退出*/checkh;/*返回二分圖標(biāo)志*/;/* check */計(jì)算和輸出沖突事件影響力的最小值proc work;var p,q,ans:longint; p1;qm;while p1.v; repeatwhile

24、ai.vx do dec(j);if ij;/repeatif hej then qsort(he,j);if i0 do9 end; /qsortbeginif find(ai.l)=find(ai.r) then begin ans:=ai.v;break;end; if (duiai.l=0) and(duiai.r=0) then beginduiai.l:=ai.r; duiai.r:=ai.l; end/then begin else beginif duiai.l0 then beginunion(duiai.l,ai.r);if duiai.r=0 then duiai.r:=

25、ai.l; end;/ifif duiai.r0 then beginunion(duiai.r,ai.l);if duiai.l=0 then duiai.l:=ai.r; end;/if end;/else begin dec(i); end;/while writeln(ans); end./main匹配的基本概念設(shè)G=V，E一個(gè)無向圖，ME是G 的若干條邊的集合。如果M中的任意兩條邊沒有公共的端點(diǎn)，則稱M是G的一個(gè)匹配。從給定的圖G=V，E的所有匹配中，把包含邊數(shù)最多的匹配找出來。這種匹配即所謂的最大匹配問題?，F(xiàn)實(shí)生活中的許多問題可以歸結(jié)為匹配問題。二分圖及二分圖的匹配二分圖是一種特殊

26、類型的圖：圖中的頂點(diǎn)集被劃分成X與Y兩個(gè)子集,圖中每條邊的兩個(gè)端點(diǎn)一定是一個(gè)屬于X而另一個(gè)屬于Y。二分圖的匹配是求邊的一個(gè)子集，該子集中的任意兩條邊都沒有公共的端點(diǎn)。計(jì)算二分圖最大匹配的匈牙利算法設(shè)M是二分圖的一個(gè)匹配，將M中的邊所關(guān)聯(lián)的頂點(diǎn)稱為蓋點(diǎn)，其余頂點(diǎn)稱為未蓋點(diǎn)。若一條路徑上屬于M的邊和不屬于M的邊交替出現(xiàn)，則稱該路徑為一條交錯(cuò)軌。若路徑p是一條起始點(diǎn)和結(jié)束點(diǎn)都是未蓋點(diǎn)的交錯(cuò)軌，則稱p為一條關(guān)于M的增廣路徑，因?yàn)橥ㄟ^MMp可使得M中的匹配邊數(shù)增加1。若二分圖中不存在關(guān)于M的增廣路徑，最后得到的匹配M就是G的一個(gè)最大匹配。取未蓋點(diǎn)t5作為樹根，頂點(diǎn)c1是樹上第一層中唯一的頂點(diǎn)，未匹配邊(

27、t5，c1)是樹上的一條邊。頂點(diǎn)t2處于樹的第二層，邊(c1，t2)屬于M且關(guān)聯(lián)于c1邊，也是樹上的又一條邊。頂點(diǎn)c5是未蓋點(diǎn)可以添加到第三層，找到了一條增廣路徑p=t5c1t2c5，得到圖G的一個(gè)更大的匹配Mp，M p是一個(gè)完全匹配，從而也是G的一個(gè)最大匹配。數(shù)據(jù)結(jié)構(gòu)const maxn = 200; /*頂點(diǎn)數(shù)的上限*/vare:array1.maxn, 0.maxn of integer; /*鄰接表，其中頂點(diǎn)i的出度為ei,0，第j條出邊的另一端點(diǎn)為ei,j*/link:array1.maxnof integer; /*匹配邊集，其中頂點(diǎn)i所在的匹配邊為（linki,i）*/ used

28、:array1.maxn of boolean;/*Y集合中頂點(diǎn)的訪問標(biāo)志*/n, m:integer; /* X集和Y集的頂點(diǎn)數(shù)各為n,邊數(shù)為m*/判斷是否存在由u出發(fā)的可增廣路徑func check(u:integer):boolean; var i, v:integer; for i1 to eu, 0 do /*枚舉u頂點(diǎn)的每一條出邊*/ veu,i; /*取出u的第i條出邊的另一端點(diǎn)v*/if not usedv /*若v未訪問，則訪問v*/then usedvtrue;if(linkv=0)or(check(linkv) /*若v的前驅(qū)是未蓋點(diǎn)或者存在由v的前驅(qū)出發(fā)的可增廣路徑，則

29、設(shè)定（u,v）為匹配邊，返回成功標(biāo)志*/then linkvu;exit(true); /*then*/;/*then*/;/*for*/exit(false); /*返回失敗標(biāo)志*/;/* check */主程序輸入二分圖信息，構(gòu)造鄰接表e；最大匹配邊數(shù)初始化為0；for i1 to n do /*枚舉X集的每個(gè)頂點(diǎn)*/ fillchar(used,sizeof(used),0);/*Y集合中的所有頂點(diǎn)未訪問標(biāo)志*/if check(i) then 最大匹配邊數(shù)+1 ;/*for*/輸出最大匹配邊數(shù);設(shè)二分圖G有e條邊，X集和Y集各有n個(gè)頂點(diǎn)，M是G的一個(gè)匹配。如果用鄰接表表示G，那么求一條

30、關(guān)于M的增廣路徑需要O(e)時(shí)間。因?yàn)槊空页鲆粭l新的增廣路徑都將得到一個(gè)更大的匹配，所以最多求n條增廣路徑就可以求出圖G的最大匹配。由此得出，總的時(shí)間復(fù)雜度為O(n*e) 。多米諾骨牌覆蓋給出一個(gè)n*n的方陣，但其中有p個(gè)點(diǎn)方格被挖掉了，告訴你這些挖去方格的坐標(biāo)。問是否能用1*2的多米骨牌將剩余的方格恰好覆蓋。輸入：第1行為方陣規(guī)模n；以下為n*n的01矩陣，0代表方格被挖掉；輸出：若成功，則輸出覆蓋剩余方格所使用的多米諾骨牌數(shù)；否則輸出0。算法分析將所有的方格類似于國(guó)際象棋盤一樣黑白間隔染色，并在有邊相鄰的兩個(gè)（未被挖去的）方格之間連邊。很明顯，白色的方格之間不可能有邊，黑色的方格之間也不可

31、能有邊。因此這是一個(gè)二分圖。而一個(gè)多米諾骨牌覆蓋的兩個(gè)方格就相當(dāng)于一條邊覆蓋了兩個(gè)點(diǎn)。因此這就是二分圖的最大（完全）覆蓋問題。直接用二分圖的最大（完全）匹配就可以了。由于這題的圖比較特殊，每個(gè)方格最多只和4個(gè)方格相鄰，圖的最大邊數(shù)2n2，因此算法的時(shí)間復(fù)雜度為O(n4)。(i,j)的黑白判斷和頂點(diǎn)序號(hào)(i,j)的黑白判斷：黑格：行列的奇偶相同（i mod 2=j mod 2）白格：行列的奇偶不同（i mod 2j mod 2）(i,j)的頂點(diǎn)序號(hào)k：k=（i-1）*n+j數(shù)據(jù)結(jié)構(gòu)constmaxn = 50; /*方陣的規(guī)模上限*/dx:array1.4of integer=(-1,1,0,0);/*dxi為i方向的水平增量*/dy:array1.4of integer=(0,0,-1,1);/*dyi為i方向的垂直增量*/vare:array1.maxn * maxn, 0.maxn * maxn of integer; /*鄰接表，其中頂點(diǎn)i的出度為ei,0，第j條出邊的另一端點(diǎn)為ei,j*/link:array1.maxn * maxn of integer