20xx年醫(yī)學(xué)專題—二分圖匹配基于匈牙利算法和km算法(編輯修改稿)
2024-11-17 22:18 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 。 //路徑取反操作。 if(t == 1 || dfs(t)) //尋找是否為增廣路徑 return true。 match[i] = t。} return false。}int main(){//........... int s = 0。 memset(match,1,sizeof(match))。 for(i = 0。 i n。 i++){ //以二分集中的較小集為n進(jìn)行匹配較優(yōu) memset(visit,0,sizeof(visit))。 if(dfs(i)) s++。 //s為匹配數(shù) }//............return 0。}二分圖最優(yōu)匹配：對(duì)于二分圖的每條邊都有一個(gè)權(quán)（非負(fù)），要求一種完備匹配方案，使得所有匹配邊的權(quán)和最大，記做最優(yōu)完備匹配。（特殊的，當(dāng)所有邊的權(quán)為1時(shí)，就是最大完備匹配問(wèn)題）解二分圖最優(yōu)匹配問(wèn)題可用窮舉的方法，但窮舉的效率=n！，所以我們需要更加優(yōu)秀的算法。先說(shuō)
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1