? ? 最大權(quán)二分匹配問(wèn)題就是給二分圖的每條邊一個(gè)權(quán)值，選擇若干不相交的邊，得到的總權(quán)值最大。解決這個(gè)問(wèn)題可以用KM算法。理解KM算法需要首先理解“可行頂標(biāo)”的概念?？尚许敇?biāo)是指關(guān)于二分圖兩邊的每個(gè)點(diǎn)的一個(gè)值lx[i]或ly[j]，保證對(duì)于每條邊w[i][j]都有l(wèi)x[i]+ly[j]-w[i][j]>=0。如果所有滿足lx[i]+ly[j]==w[i][j]的邊組成的導(dǎo)出子圖中存在一個(gè)完美匹配，那么這個(gè)完美匹配肯定就是原圖中的最大權(quán)匹配。理由很簡(jiǎn)單：這個(gè)匹配的權(quán)值之和恰等于所有頂標(biāo)的和，由于上面的那個(gè)不等式，另外的任何匹配方案的權(quán)值和都不會(huì)大于所有頂標(biāo)的和。

? ? 但問(wèn)題是，對(duì)于當(dāng)前的頂標(biāo)的導(dǎo)出子圖并不一定存在完美匹配。這時(shí)，可以用某種方法對(duì)頂標(biāo)進(jìn)行調(diào)整。調(diào)整的方法是：根據(jù)最后一次不成功的尋找交錯(cuò)路的DFS，取所有i被訪問(wèn)到而j沒(méi)被訪問(wèn)到的邊(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。將交錯(cuò)樹中的所有左端點(diǎn)的頂標(biāo)減小d，右端點(diǎn)的頂標(biāo)增加d。經(jīng)過(guò)這樣的調(diào)整以后：原本在導(dǎo)出子圖里面的邊，兩邊的頂標(biāo)都變了，不等式的等號(hào)仍然成立，仍然在導(dǎo)出子圖里面；原本不在導(dǎo)出子圖里面的邊，它的左端點(diǎn)的頂標(biāo)減小了，右端點(diǎn)的頂標(biāo)沒(méi)有變，而且由于d的定義，不等式仍然成立，所以他就可能進(jìn)入了導(dǎo)出子圖里。

? ? 初始時(shí)隨便指定一個(gè)可行頂標(biāo)，比如說(shuō)lx[i]=max{w[i][j]|j是右邊的點(diǎn)}，ly[i]=0。然后對(duì)每個(gè)頂點(diǎn)進(jìn)行類似Hungary算法的find過(guò)程，如果某次find沒(méi)有成功，則按照這次find訪問(wèn)到的點(diǎn)對(duì)可行頂標(biāo)進(jìn)行上述調(diào)整。這樣就可以逐步找到完美匹配了。

? ? 值得注意的一點(diǎn)是，按照上述d的定義去求d的話需要O(N^2)的時(shí)間，因?yàn)閐需要被求O(N^2)次，這就成了算法的瓶頸?？梢赃@樣優(yōu)化：設(shè)slack[j]表示右邊的點(diǎn)j的所有不在導(dǎo)出子圖的邊對(duì)應(yīng)的lx[i]+ly[j]-w[i][j]的最小值，在find過(guò)程中，若某條邊不在導(dǎo)出子圖中就用它對(duì)相應(yīng)的slack值進(jìn)行更新。然后求d只要用O(N)的時(shí)間找到slack中的最小值就可以了。

? ? 如果是求最小權(quán)匹配，只需要把那個(gè)不等式反一下就行了。算法需要作出的改變是：lx的初值為所有臨界邊中的最小值，find中t反號(hào)。

最大權(quán)匹配

/* hdu 2255 奔小康賺大錢 題意：有n個(gè)村民n個(gè)房子，每個(gè)村名對(duì)每個(gè)房子都有一個(gè)報(bào)價(jià)，求報(bào)價(jià)和最大的安排最大權(quán)匹配 也就是最優(yōu)匹配這兒有個(gè)KM算法的講解 http://blog.csdn.net/hqd_acm/article/details/5829682 http://www.byvoid.com/blog/tag/%E6%9C%80%E5%B0%8F%E6%9D%83%E5%8C%B9%E9%85%8D/zh-hant/ */ #include<stdio.h> #include<string.h> #define N 305 int map[N][N],match[N],lx[N],ly[N],slack[N],visx[N],visy[N]; int n; int hungray(int i)//適應(yīng)KM算法的 匈牙利算法 {int j;visx[i]=1;for(j=1;j<=n;++j)//{if(visy[j]) continue;if(lx[i]+ly[j]==map[i][j])//若j在相等子圖里 與普通匈牙利算法一樣{visy[j]=1;if(match[j]==-1||hungray(match[j])){match[j]=i;return 1;}}else if(slack[j]>(lx[i]+ly[j]-map[i][j]))//不在相等子圖里 并且可以使slack更小 更新之slack[j]=lx[i]+ly[j]-map[i][j];}return 0; } int km() {memset(match, -1, sizeof(match)); int i,j,d;memset(lx,0,sizeof(lx));memset(ly,0,sizeof(ly));for(i=1;i<=n;i++)//lx取與i連接的邊的最大權(quán)for(j=1;j<=n;++j)if(map[i][j]>lx[i]) lx[i]=map[i][j];for(i=1;i<=n;++i)//對(duì)每一個(gè)點(diǎn)進(jìn)行匹配{for(j=1;j<=n;j++)//對(duì)每一個(gè)點(diǎn)來(lái)說(shuō)，需要一直更新lx、ly 直到找到交錯(cuò)路 slack存的是那個(gè)較小的差值，所以求每個(gè)點(diǎn)前初始化成最大slack[j]=0x7fffffff;while(1)//當(dāng)找到交錯(cuò)路的時(shí)候 跳出{memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));//初始化訪問(wèn)標(biāo)記if(hungray(i))break;d=0x7fffffff;//尋找最小的改變量for(j=1;j<=n;++j)if(!visy[j]&&slack[j]<d) d=slack[j];for(j=1;j<=n;++j)//改變{if(visx[j]) lx[j]-=d;if(visy[j]) ly[j]+=d;else slack[j]-=d;//對(duì)于通過(guò)這次更新頂標(biāo)而進(jìn)入相等子圖的j來(lái)說(shuō)，這不已經(jīng)沒(méi)有意義//但是 對(duì)于還沒(méi)有進(jìn)入相等子圖的j來(lái)說(shuō) 他們相連的i已經(jīng)-d了，所以那個(gè)差會(huì)減小d 故這里修改slack}}}d=0;for(i=1;i<=n;i++)//所有邊的權(quán)都表示在了點(diǎn)上d+=lx[i],d+=ly[i];return d; } int main() {int i,j;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=n;++j)scanf("%d",&map[i][j]);printf("%d\n",km());}return 0; }
最小權(quán)匹配

/* poj 2195 Going Home學(xué)習(xí)了二分圖匹配，所以又用 最小權(quán)匹配 些了一邊，比 最小費(fèi)用最大流 快了一些最小權(quán)匹配 與最大權(quán)匹配差不多只需要把 邊的權(quán)取相反數(shù)然后過(guò)程跟最大權(quán)匹配一樣最后 邊權(quán)和 是一個(gè)負(fù)數(shù) 再取相反數(shù)即可*/ #include<iostream> #include<cmath> using namespace std; int m,n; struct node//表示人或房子位置 {int x,y; }; struct edge//用鄰接表存邊 {int v,f,next; }e[100000]; node *man,*house;//人和房子的數(shù)組 int *match,*lx,*ly,*slack,*visx,*visy,*head,nman;//匹配 x的頂標(biāo) y的頂標(biāo) 優(yōu)化數(shù)組 x訪問(wèn)標(biāo)志 y訪問(wèn)標(biāo)志 鄰接表頭節(jié)點(diǎn) 人的數(shù)量 char map[110][110]; int hungray(int i)//匈牙利算法 {int j,v;visx[i]=1;for(j=head[i];j!=-1;j=e[j].next){v=e[j].v;if(visy[v]) continue;if(lx[i]+ly[v]==e[j].f){visy[v]=1;if(match[v]==-1||hungray(match[v])){match[v]=i;return 1;}}else if(slack[v]>lx[i]+ly[v]-e[j].f)slack[v]=lx[i]+ly[v]-e[j].f;}return 0; } int km()//km {memset(match,-1,sizeof(int)*nman);int i,j,d;memset(ly,0,sizeof(int)*nman);for(i=0;i<nman;++i){for(j=0;j<nman;++j)slack[j]=0x7fffffff;while(1){memset(visx,0,sizeof(int)*nman);memset(visy,0,sizeof(int)*nman);if(hungray(i))break;d=0x7fffffff;for(j=0;j<nman;++j)if(!visy[j]&&slack[j]<d) d=slack[j];for(j=0;j<nman;++j){if(visx[j]) lx[j]-=d;if(visy[j]) ly[j]+=d;else slack[j]-=d;}}}d=0;for(i=0;i<nman;++i)d+=lx[i],d+=ly[i];return -d;//取相反數(shù) } int main() {int i,j,yong;while(cin>>n>>m,m+n){nman=0;//初始化yong=0;for(i=0;i<n;++i)//讀數(shù)據(jù)for(j=0;j<m;++j){cin>>map[i][j];if(map[i][j]=='m')nman++;}match=new int[nman];//申請(qǐng)空間man=new node[nman];//house=new node[nman];//lx=new int[nman];//ly=new int[nman];//slack=new int[nman];//visx=new int[nman];//visy=new int[nman];//head=new int[nman];//int jman=0,jhouse=0;for(i=0;i<n;++i)//統(tǒng)計(jì)人和房子的位置for(j=0;j<m;++j){if(map[i][j]=='m'){man[jman].x=i;man[jman++].y=j;}else if(map[i][j]=='H'){house[jhouse].x=i;house[jhouse++].y=j;}}memset(head,-1,sizeof(int)*nman);//計(jì)算人和房子的距離 建邊f(xié)or(i=0;i<nman;++i){int max=-(0x7fffffff);//在計(jì)算的同時(shí)給lx數(shù)組賦值，就是和i相連的邊的最大權(quán)for(j=0;j<nman;++j){e[yong].v=j;e[yong].f=-(abs(man[i].x-house[j].x)+abs(man[i].y-house[j].y));//因?yàn)榍笞钚?quán)匹配 所以用權(quán)的相反數(shù)if(max<e[yong].f) max=e[yong].f;//更新maxe[yong].next=head[i];head[i]=yong++;}lx[i]=max;//給lx賦值}cout<<km()<<endl;//計(jì)算 輸出delete[] match;//釋放空間delete[] man;delete[] house;delete[] lx;delete[] ly;delete[] slack;delete[] visx;delete[] visy;delete[] head;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的KM算法 最优匹配(最大权匹配) hdu 2255 奔小康赚大钱 最小权匹配 poj 2195 Going Home的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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