有個博客理解起來很棒，描述的生動形象，插眼：https://blog.csdn.net/chenshibo17/article/details/79933191

用處：給定一張二分圖，二分圖的每一條邊都帶有一個權(quán)值，求出該二分圖的一組最大匹配，使得匹配邊的權(quán)值總和最大，注意，二分圖帶權(quán)最大匹配的前提是匹配數(shù)最大，然后再最大化匹配邊的權(quán)值總和

局限性：只能滿足“帶權(quán)最大匹配一定是完備匹配”的圖中正確求解，完備匹配就是給定一張二分圖，其左部、右部節(jié)點數(shù)相同，均為N個節(jié)點。如果該二分圖的最大匹配包含N條匹配邊，則稱該二分圖具有完備匹配

時間復雜度：N^4，隨機數(shù)據(jù)N^3

注意：我現(xiàn)在的理解是因為KM的局限性太大，并且時間復雜度也不太優(yōu)秀，基本上所有可以用KM解決的問題都可以用費用流來解決，所以僅了解一下KM的定義和模板，后續(xù)會繼續(xù)學習網(wǎng)絡流

代碼：

const int N=310;int n;int la[N],lb[N];//頂標bool visa[N],visb[N];//訪問標記int maze[N][N];//邊權(quán)int match[N];//右部點匹配了哪一個左部點int upd[N];bool dfs(int x) {visa[x]=true;//訪問標記：x在交錯樹中for(int i=1;i<=n;i++){if(!visb[i]){if(la[x]+lb[i]-maze[x][i]==0)//相等子圖{visb[i]=true;//訪問標記：y在交錯樹中if(!match[i]||dfs(match[i])){match[i]=x;return true;}}elseupd[i]=min(upd[i],la[x]+lb[i]-maze[x][i]);}}return false; } int KM() {memset(match,0,sizeof(match));for(int i=1;i<=n;i++){la[i]=-inf;lb[i]=0;for(int j=1;j<=n;j++)la[i]=max(la[i],maze[i][j]);}for(int i=1;i<=n;i++){while(1)//直到左部點找到匹配{memset(visa,false,sizeof(visa));memset(visb,false,sizeof(visb));memset(upd,inf,sizeof(upd));if(dfs(i))break;int delta=inf;for(int j=1;j<=n;j++)if(!visb[j])delta=min(delta,upd[j]);for(int j=1;j<=n;j++)//修改頂標{if(visa[j])la[j]-=delta;if(visb[j])lb[j]+=delta;}}}int ans=0;for(int i=1;i<=n;i++)ans+=maze[match[i]][i];return ans; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結(jié)

以上是生活随笔為你收集整理的二分图最大权匹配算法KM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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