二分圖最大匹配問題(貪心算法)

二分圖最大匹配問題

(貪心算法)BY長郡中學(xué)曹博凱二分圖的基本概念二分圖是一類特殊的圖結(jié)構(gòu)二分圖是這樣一種圖：G的頂點(diǎn)集合V分成兩部分X與Y，G中每條邊的兩個(gè)端點(diǎn)一定是一個(gè)屬于X而另一個(gè)屬于Y。匹配的基本概念設(shè)G=[V，E]是一個(gè)無向圖，M屬于E是G的若干條邊的集合，如果M中的任意兩條邊都沒有公共的端點(diǎn)，就稱M是一個(gè)匹配。最大匹配的基本概念從給定的圖G=[V，E]的所有匹配中，把包含邊數(shù)最多的匹配找出來。這種匹配即所謂的最大匹配問題。二分圖的最大匹配e.g.飛行員分成兩部分，一部分是正駕駛員，一部分是副駕駛員。顯然，如何搭配正副駕駛員才能使出航飛機(jī)最多的問題可以歸結(jié)為一個(gè)二分圖上的最大匹配問題。常用算法網(wǎng)絡(luò)流算法（編程復(fù)雜，小題大做）匈牙利算法（理解困難，實(shí)現(xiàn)簡單）以上這些我都不會怎么辦？不用急！貪心算法下面，我們引進(jìn)一種能夠完美解決二分圖最大匹配問題的貪心算法。理解容易實(shí)現(xiàn)不難會議安排一個(gè)重要的會議由A公司的M位代表和B公司的N位代表參加（M，N≤1000，代表用1，2，……，M和1，2，……，N表示）。他們被預(yù)先分成K(K≤60000)組進(jìn)行談判。每組兩個(gè)人分別來自A公司和B公司。每個(gè)參加會議的代表都至少參加了一組談判。會議為每一個(gè)代表都準(zhǔn)備了一個(gè)房間。技術(shù)人員將會在一些房間之間連上直通電話，一個(gè)代表至少要和他的一個(gè)談判對手直接聯(lián)絡(luò)。連接一個(gè)直通電話的價(jià)格是常數(shù)。技術(shù)人員要用盡量少的花費(fèi)滿足會議的要求。題目分析這道題目我們很容易將其抽象成為二分圖最大匹配的基本模型。我們可以用匈牙利算法求出其最大匹配M，然后所求解即為n+m-M?？墒牵紙錾喜⒉皇敲總€(gè)人都能想到這一巧妙的轉(zhuǎn)換。于是，我們可以懷抱著一種騙分的心態(tài)，構(gòu)造出一種貪心策略，從而得到滿分！貪心算法首先，我們將每條無向邊拆分成兩條反向的有向邊，存儲在鄰接表中。與此同時(shí)，我們記錄下每個(gè)頂點(diǎn)的出度。然后，我們每次找出一個(gè)當(dāng)前未被訪問過的結(jié)點(diǎn)中，出度最小的結(jié)點(diǎn)u。同時(shí)，再在以該結(jié)點(diǎn)u為起始點(diǎn)的所有邊所對的點(diǎn)中，找出一個(gè)同樣滿足未被訪問，且出度最小的結(jié)點(diǎn)v。貪心算法接著，我們將u,v兩點(diǎn)都進(jìn)行刪除操作。（當(dāng)u的出邊所對的點(diǎn)都已被訪問，那么就找不到滿足條件的v，因此只對u進(jìn)行操作）所謂刪除操作，在這里，刪除s，其實(shí)就是將s的所有出邊所對的點(diǎn)t的出度都減一。（因?yàn)橐獎(jiǎng)h除點(diǎn)s，即(s,t)也被刪除，即(t,s)也要被刪除，所以t的出度要減一）貪心算法這樣循環(huán)做下來，我們每做一次都相當(dāng)于連了一條邊（u,v），于是inc(ans)。同時(shí)，我們對這條邊的兩個(gè)端點(diǎn)u,v都做了刪除操作（如果可以的話）。每刪一個(gè)點(diǎn)就inc(tot)，直到tot=n+m，即兩邊的點(diǎn)均被刪完。此時(shí)我們得到的ans值即為答案，直接輸出即可?？偨Y(jié)以上就是簡單明了的二分圖最大匹配的貪心算法。比起前面所提到的網(wǎng)絡(luò)流算法和匈牙利算法，都有著無可比擬的優(yōu)越性。它不但比前面兩個(gè)算法都要好理解，而且不及網(wǎng)絡(luò)流算法的編程復(fù)雜度，也不用擔(dān)心匈牙利算法的遞歸層數(shù)。注意以上所述的貪心算法僅適用于二分圖的最大匹配問題，最佳匹配問題是不適用的。本人尚未見到有人能夠?qū)Υ怂惴ńo出嚴(yán)格的證明，但是網(wǎng)上確實(shí)也有不少人有用此算法過全點(diǎn)的經(jīng)歷?？傊?，請各位慎重使用！（：以下附例題的主程序的代碼主程序代碼procedureadd(i,j:longint);begin

inc(top);

v[top]:=j;

next[top]:=u[i];

u[i]:=top;

inc(degree[i]);end;procedureins(i:longint);var

o:longint;begin

visit[i]:=true;

inc(tot);o:=u[i];whileo<>0dobegin

dec(degree[v[o]]);o:=next[o];end;end;begin

readln(n,m,k);fora:=1tokdobegin

readln(b,c);c:=n+c;

add(b,c);

add(c,b);end;主程序代碼

n:=n+m;whiletot<ndobeginb:=maxlongint;//找結(jié)點(diǎn)ufora:=1tondoif(not

visit[a])and(degree[a]<b)thenbeginb:=degree[a];c:=a;end;a:=u[c];b:=maxlongint;//找結(jié)點(diǎn)vwhilea<>0dobegin

if(not

visit[v[a]])and(degree[v[a]]<b)thenbeginb:=degree[v[a]];d:=v[a];end;a:=next[a];end;

inc(ans);//連邊，答案加一

in