最大二分圖匹配

1、最大二分圖匹配.txt人永遠(yuǎn)不知道誰哪次不經(jīng)意的跟你說了再見之后就真的再也不見了。一分鐘有多長？這要看你是蹲在廁所里面，還是等在廁所外面最大二分圖匹配 (匈牙利算法) 實(shí)現(xiàn)最近隊(duì)里流行二分圖,不能落下,呵呵我也看了。二分圖指的是這樣一種圖：其所有的頂點(diǎn)分成兩個(gè)集合M和N，其中M或N中任意兩個(gè)在同一集合中的點(diǎn)都不相連。二分圖匹配是指求出一組邊，其中的頂點(diǎn)分別在兩個(gè)集合中，并且任意兩條邊都沒有相同的頂點(diǎn)，這組邊叫做二分圖的匹配，而所能得到的最大的邊的個(gè)數(shù)，叫做最大匹配。計(jì)算二分圖的算法有網(wǎng)絡(luò)流算法和匈牙利算法（目前就知道這兩種），其中匈牙利算法是比較巧妙的，具體過程如下（轉(zhuǎn)自組合數(shù)學(xué)）：令g=（x

2、,*,y）是一個(gè)二分圖，其中x=x1,x2.,y=y1,y2,.令m為g中的任意匹配。1。將x的所有不與m的邊關(guān)聯(lián)的頂點(diǎn)表上￥，并稱所有的頂點(diǎn)為未掃描的。轉(zhuǎn)到2。2。如果在上一步?jīng)]有新的標(biāo)記加到x的頂點(diǎn)上，則停，否則 ，轉(zhuǎn)33。當(dāng)存在x被標(biāo)記但未被掃描的頂點(diǎn)時(shí)，選擇一個(gè)被標(biāo)記但未被掃描的x的頂點(diǎn)，比如xi，用（xi）標(biāo)記y 的所有頂點(diǎn)，這些頂點(diǎn)被不屬于m且尚未標(biāo)記的邊連到xi?，F(xiàn)在頂點(diǎn)xi 是被掃描的。如果不存在被標(biāo)記但未被掃描的頂點(diǎn)，轉(zhuǎn)4。4。如果在步驟3沒有新的標(biāo)記被標(biāo)記到y(tǒng)的頂點(diǎn)上，則停，否則轉(zhuǎn)5。5。當(dāng)存在y被標(biāo)記但未被掃描的頂點(diǎn)時(shí)。選擇y的一個(gè)被標(biāo)記但未被掃描的頂點(diǎn)，比如yj，用（y

3、j）標(biāo)記x的頂點(diǎn)，這些頂點(diǎn)被屬于m且尚未標(biāo)記的邊連到y(tǒng)j?，F(xiàn)在，頂點(diǎn)yj是被掃描的。如果不存在被標(biāo)記但未被掃描的頂點(diǎn)則轉(zhuǎn)道2。由于每一個(gè)頂點(diǎn)最多被標(biāo)記一次且由于每一個(gè)頂點(diǎn)最多被掃描一次，本匹配算法在有限步內(nèi)終止。代碼實(shí)現(xiàn)：bfs過程：#include<stdio.h>#include<string.h>main()bool map100300;inti,i1,i2,num,num1,que300,cou,stu,match1100,match2300,pque,p1,now,prev300,n;scanf("%d",&n);for(i=0;i

4、<n;i+)scanf("%d%d",&cou,&stu);memset(map,0,sizeof(map);for(i1=0;i1<cou;i1+)scanf("%d",&num);for(i2=0;i2<num;i2+)scanf("%d",&num1);mapi1num1-1=true;num=0;memset(match1,int(-1),sizeof(match1);memset(match2,int(-1),sizeof(match2);for(i1=0;i1<cou

5、;i1+)p1=0;pque=0;for(i2=0;i2<stu;i2+)if(mapi1i2)previ2=-1;quepque+=i2;elseprevi2=-2;while(p1<pque)now=quep1;if(match2now=-1)break;p1+;for(i2=0;i2<stu;i2+)if(previ2=-2&&mapmatch2nowi2)previ2=now;quepque+=i2;if(p1=pque)continue;while(prevnow>=0)match1match2prevnow=now; match2now=ma

6、tch2prevnow; now=prevnow;match2now=i1;match1i1=now;num+;if(num=cou)printf("YESn");elseprintf("NOn");dfs實(shí)現(xiàn)過程：#include<stdio.h>#include<string.h>#define MAX 100bool mapMAXMAX,searchedMAX; int prevMAX,m,n;bool dfs(int data)int i,temp;for(i=0;i<m;i+)if(mapdatai&&am

7、p;!searchedi) searchedi=true;temp=previ;previ=data;if(temp=-1|dfs(temp)return true;previ=temp;return false;main()int num,i,k,temp1,temp2,job;while(scanf("%d",&n)!=EOF&&n!=0) scanf("%d%d",&m,&k);memset(map,0,sizeof(map);memset(prev,int(-1),sizeof(prev); memset(searched,0,sizeof(searched); for(i=0;i<k;i+)scanf("%d%d%d",&job,&temp1,&temp2); if(temp1!=0&&temp2!=0)maptemp1temp2=true;num=0;for(i=