??? 首先介紹一下題意：已知，有N個(gè)學(xué)生和P門(mén)課程，每個(gè)學(xué)生可以選0門(mén)，1門(mén)或者多門(mén)課程，要求在N個(gè)學(xué)生中選出P個(gè)學(xué)生使得這P個(gè)學(xué)生與P門(mén)課程一一對(duì)應(yīng)。

??? 這個(gè)問(wèn)題既可以利用最大流算法解決也可以用匈牙利算法解決。如果用最大流算法中的Edmonds-karp算法解決，因?yàn)闀r(shí)間復(fù)雜度為O(n*m*m),n為點(diǎn)數(shù)，m為邊數(shù)，會(huì)超時(shí)，利用匈牙利算法，時(shí)間復(fù)雜度為O(n*m)，時(shí)間復(fù)雜度小，不會(huì)超時(shí)。

???? 其實(shí)匈牙利算法就是最大流算法，只不過(guò)它的使用范圍僅限于二分圖，所以可以稱(chēng)之為“二分圖定制版的最大流算法”，既然是定制的，那么他就會(huì)考慮到二分圖的特殊性，優(yōu)化原來(lái)的最大流算法，降低時(shí)間復(fù)雜度，同時(shí)也變得有點(diǎn)復(fù)雜不容易理解了。既然匈牙利算法繼承自最大流算法，所以他的算法框架與最大流算法是一樣的：

最大流算法與匈牙利算法的框架：

初始時(shí)最大流為0（匈牙利算法為：最大匹配為空）

while 找到一條增廣路徑（匈牙利算法為：取出未遍歷的左邊的點(diǎn)u）

?????? 最大流+=增廣路徑的流量，更新網(wǎng)絡(luò)（匈牙利算法為：如果點(diǎn)u存在增廣路徑，增廣路徑取反，最大匹配增加1對(duì)匹配）

?? 我們知道在利用最大流算法解決最大匹配問(wèn)題時(shí)，首先需要構(gòu)建一個(gè)超級(jí)源點(diǎn)s和超級(jí)匯點(diǎn)t，并且邊是有方向的和容量（為1）的(如圖8所示)，而利用匈牙利算法則不需要構(gòu)造s,t，邊也沒(méi)有方向和容量。表面上看匈牙利算法中的邊沒(méi)有方向和容量，其實(shí)在它對(duì)增廣路徑的約束中我們可以看到邊的方向和容量的“影子”，如下紅色標(biāo)注的約束。

? 匈牙利算法對(duì)增廣路徑的約束 參見(jiàn)[1] ：

? (1)有奇數(shù)條邊。
? (2)起點(diǎn)在二分圖的左半邊，終點(diǎn)在右半邊。
? (3)路徑上的點(diǎn)一定是一個(gè)在左半邊，一個(gè)在右半邊，交替出現(xiàn)。（其實(shí)二分圖的性質(zhì)就決定了這一點(diǎn)，因?yàn)槎謭D同一邊的點(diǎn)之間沒(méi)有邊相連，不要忘記哦。）
? (4)整條路徑上沒(méi)有重復(fù)的點(diǎn)。
? (5)起點(diǎn)和終點(diǎn)都是目前還沒(méi)有配對(duì)的點(diǎn)，而其它所有點(diǎn)都是已經(jīng)配好對(duì)的。（如圖5，圖6所示，［2,5］是已經(jīng)配好對(duì)的點(diǎn)；而起點(diǎn)3和終點(diǎn)7目前還沒(méi)有與其它點(diǎn)配對(duì)。）
? (6)路徑上的所有第奇數(shù)條邊都不在原匹配中，所有第偶數(shù)條邊都出現(xiàn)在原匹配中。（如圖5，圖6所示，原有的匹配［2，5］在在圖6給出的增廣路徑（紅線(xiàn)所示）中是第2條邊。而增廣路徑的第1、3條邊都沒(méi)有出現(xiàn)在圖5給出的匹配中。）
? (7)最后，也是最重要的一條，把增廣路徑上的所有第奇數(shù)條邊加入到原匹配中去，并把增廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱(chēng)為增廣路徑的取反），則新的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。（如圖6所示，新的匹配就是所有被紅色的邊所覆蓋的黑色的邊，而所有紅色的邊所覆蓋的黃色的邊則從原匹配中刪除，最終匹配結(jié)果如圖7黃色的邊所示。則新的匹配數(shù)為3。）

? 為了便于理解，下面給出利用最大流算法和匈牙利算法解決最大二分匹配的圖示。圖1為初始二分圖，圖1->圖7為利用匈牙利算法求解最大二分匹配的過(guò)程，圖8為利用圖1二分圖所構(gòu)建的流網(wǎng)絡(luò)，圖8->圖14為利用最大流算法求解最大二分匹配的過(guò)程,最終求得的最大流為所有增廣路徑（如圖9，圖10，圖11所示）增加的流相加：1+1+1=3。

?? 下面介紹一下Hopcroft-Karp算法，這個(gè)算法的時(shí)間復(fù)雜度為O(n^(1/2)*m)。該算法是對(duì)匈牙利算法的優(yōu)化，如圖1-圖7，利用匈牙利算法一次只能找到一條增廣路徑，Hopcroft-Karp就提出一次找到多條不相交的增廣路徑（不相交就是沒(méi)有公共點(diǎn)和公共邊的增廣路徑），然后根據(jù)這些增廣路徑添加多個(gè)匹配。說(shuō)白了，就是批量處理！為了容易理解，我構(gòu)造了一個(gè)圖例，見(jiàn)圖15-圖18。

?

??

回到原題中來(lái)，code1、code2分別為dfs和bfs實(shí)現(xiàn)的匈牙利算法;code3為利用Hopcroft-Karp解決COURSE的代碼。

code1:

#include<iostream>using namespace std; #define Maxn 500 //課程與課代表 //存儲(chǔ)左側(cè)的點(diǎn)連接的右側(cè)點(diǎn) int lefts[Maxn]; //存儲(chǔ)右側(cè)的點(diǎn) 連接的左側(cè)點(diǎn) int rights[Maxn]; int flag_rights[Maxn]; int G[Maxn][Maxn]; //nc代表課程數(shù)目 ns代表學(xué)生數(shù)目 int nc,ns;int findpath(int left_u) {for(int v=1;v<=ns;v++){if(G[left_u][v]&&!flag_rights[v]){flag_rights[v]=1;if((rights[v]==-1||findpath(rights[v]))){lefts[left_u]=v;rights[v]=left_u;return 1; }} }return 0; }//最大匹配 int MaxMatch() {// printf("MaxMatch開(kāi)始執(zhí)行\(zhòng)n");int cnt=0;memset(lefts,-1,sizeof(lefts));memset(rights,-1,sizeof(rights));for(int u=1;u<=nc;u++){memset(flag_rights,0,sizeof(flag_rights));if(findpath(u)){cnt++;}} return cnt; }int main() {int num;scanf("%d",&num);while(num--){//首先輸入數(shù)據(jù) memset(G,0,sizeof(G));scanf("%d%d",&nc,&ns);for(int u=1;u<=nc;u++){int c_stu;scanf("%d",&c_stu);for(int j=0;j<c_stu;j++){int v;scanf("%d",&v);G[u][v]=1;}}if(ns>=nc&&MaxMatch()==nc){printf("YES\n");} else{printf("NO\n");}}return 0; }/* 4 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1*/ View Code

?CODE2:

#include<iostream> #include<queue> #define Maxn 500 using namespace std; //利用匈牙利算法解決二分圖匹配問(wèn)題 int nc,ns;//nc代表課程數(shù) ns代表學(xué)生數(shù) int lefts[Maxn];//存儲(chǔ)課程所對(duì)應(yīng)的學(xué)生 int rights[Maxn];//存儲(chǔ)學(xué)生所對(duì)應(yīng)的課程 int G[Maxn][Maxn]; int pre_left[Maxn];//記錄課程前面的課程 （增廣路徑） int mark_right[Maxn];//記錄當(dāng)前學(xué)生是否已經(jīng)遍歷（增廣路徑） //利用廣度優(yōu)先搜索 得到最大匹配數(shù) int max_match() { //lefts 數(shù)組初始化為0 memset(lefts,-1,sizeof(lefts)); memset(rights,-1,sizeof(rights)); int maxf=0; for(int i=1;i<=nc;i++) { queue<int>q; q.push(i); int ok=0; memset(mark_right,0,sizeof(mark_right)); memset(pre_left,0,sizeof(pre_left)); while(!q.empty()) { int u=q.front(); q.pop(); for(int v=1;v<=ns;v++) { if(G[u][v]&&!mark_right[v])//如果課程與學(xué)生對(duì)應(yīng) 并且當(dāng)前學(xué)生沒(méi)有被遍歷 { mark_right[v]=1; if(rights[v]==-1) { ok=1; //更新匹配關(guān)系 int sl=u,sr=v; while(sl!=0) { int st=lefts[sl]; lefts[sl]=sr;rights[sr]=sl; sl=pre_left[sl];sr=st; } break; } else { pre_left[rights[v]]=u;//記錄課程的前驅(qū) q.push(rights[v]); } } } if(ok) break; } if(ok) maxf++; } /* for(int i=1;i<4;i++) cout<<lefts[i]<<" "<<rights[i]<<endl; */ return maxf; } int main() { int num; scanf("%d",&num); while(num--) { memset(G,0,sizeof(G)); scanf("%d%d",&nc,&ns); for(int i=1;i<=nc;i++) { int snum; scanf("%d",&snum); int u; for(int j=1;j<=snum;j++) { scanf("%d",&u); G[i][u]=1; } } if(max_match()==nc) { printf("YES\n"); } else { printf("NO\n"); } /* cout<<"最大匹配數(shù)是："<<max_match()<<endl; cout<<"對(duì)應(yīng)的匹配關(guān)系是："<<endl; for(int i=1;i<=nc;i++) { cout<<i<<" "<<lefts[i]<<endl; } cout<<"!!!!!!!!!!!!!!"<<endl; for(int i=1;i<=ns;i++) { cout<<rights[i]<<" "<<i<<endl; }*/ } return 0; } /* 6 3 3 2 1 3 2 1 3 1 1 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1 3 3 3 1 2 3 2 1 2 1 1 */ View Code

CODE3:

#include<iostream> #include<queue> using namespace std; const int MAXN=500;// 最大點(diǎn)數(shù) const int INF=1<<28;// 距離初始值 int bmap[MAXN][MAXN];//二分圖 int cx[MAXN];//cx[i]表示左集合i頂點(diǎn)所匹配的右集合的頂點(diǎn)序號(hào) int cy[MAXN]; //cy[i]表示右集合i頂點(diǎn)所匹配的左集合的頂點(diǎn)序號(hào) int nx,ny; int dx[MAXN]; int dy[MAXN]; int dis; bool bmask[MAXN]; //尋找 增廣路徑集 bool searchpath() { queue<int>Q; dis=INF; memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(int i=1;i<=nx;i++) { //cx[i]表示左集合i頂點(diǎn)所匹配的右集合的頂點(diǎn)序號(hào) if(cx[i]==-1) { //將未遍歷的節(jié)點(diǎn) 入隊(duì) 并初始化次節(jié)點(diǎn)距離為0 Q.push(i); dx[i]=0; } } //廣度搜索增廣路徑 while(!Q.empty()) { int u=Q.front(); Q.pop(); if(dx[u]>dis) break; //取右側(cè)節(jié)點(diǎn) for(int v=1;v<=ny;v++) { //右側(cè)節(jié)點(diǎn)的增廣路徑的距離 if(bmap[u][v]&&dy[v]==-1) { dy[v]=dx[u]+1; //v對(duì)應(yīng)的距離 為u對(duì)應(yīng)距離加1 if(cy[v]==-1) dis=dy[v]; else { dx[cy[v]]=dy[v]+1; Q.push(cy[v]); } } } } return dis!=INF; } //尋找路徑 深度搜索 int findpath(int u) { for(int v=1;v<=ny;v++) { //如果該點(diǎn)沒(méi)有被遍歷過(guò) 并且距離為上一節(jié)點(diǎn)+1 if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1) { //對(duì)該點(diǎn)染色 bmask[v]=1; if(cy[v]!=-1&&dy[v]==dis) { continue; } if(cy[v]==-1||findpath(cy[v])) { cy[v]=u;cx[u]=v; return 1; } } } return 0; } //得到最大匹配的數(shù)目 int MaxMatch() { int res=0; memset(cx,-1,sizeof(cx)); memset(cy,-1,sizeof(cy)); while(searchpath()) { memset(bmask,0,sizeof(bmask)); for(int i=1;i<=nx;i++) { if(cx[i]==-1) { res+=findpath(i); } } } return res; } int main() { int num; scanf("%d",&num); while(num--) { memset(bmap,0,sizeof(bmap)); scanf("%d%d",&nx,&ny); for(int i=1;i<=nx;i++) { int snum; scanf("%d",&snum); int u; for(int j=1;j<=snum;j++) { scanf("%d",&u); bmap[i][u]=1; // bmap[u][i]=1; } } // cout<<MaxMatch()<<endl; if(MaxMatch()==nx) { printf("YES\n"); } else { printf("NO\n"); } } //system("pause"); return 0; } /* 2 3 4 2 1 3 3 1 3 4 1 2 */ View Code

?

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/penseur/archive/2013/06/16/3138981.html

總結(jié)

以上是生活随笔為你收集整理的利用匈牙利算法Hopcroft-Karp算法解决二分图中的最大二分匹配问题 例poj 1469 COURSES...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。