在復習匈牙利算法的時候，發(fā)現(xiàn)這么一篇介紹匈牙利算法的文章，非常通俗易懂，所以就借鑒過來了。

? ? ?復雜度：鄰接矩陣：O（v^3）鄰接表：O（V*E）

　　附上鏈接：趣寫算法系列之--匈牙利算法

　　下面就附上代碼吧：

　　

int maxn;//maxn 為x、y集合的最大頂點數(shù) int xmatch[maxn]; //xmatch[i]表示X集合中的i在Y集合中對應的匹配 int ymatch[maxn]; //ymatch[i]表示Y集合中的i在X集合中對應的匹配int map[maxn][maxn]; //鄰接矩陣，若i與j不相連，則為0 bool used[maxn]; //用于標記是否某點被遍歷過 int n,m; //X集合個數(shù)n，Y集合個數(shù)mbool find(int x){for(int i=0;i<m;i++){if(map[x][i] && !used[i]){used[i]=1;if(ymatch[i]=-1 || find(ymatch[i])){ymatch[i]=x;return true;}}}return false; }int hungary(){int cnt=0; //最大匹配數(shù)目memset(ymatch,-1,sizeof(ymatch));for(int i=0;i<n;i++){memset(used,0,sizeof(used));if(find[i]){cnt++;}}return cnt; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenxiwenruo/p/4511166.html

總結(jié)

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

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