---------------------以上轉(zhuǎn)自ByVoid神牛博客，并有所省略。

---

? [二分圖帶權(quán)匹配與最佳匹配] 什么是二分圖的帶權(quán)匹配？二分圖的帶權(quán)匹配就是求出一個(gè)匹配集合，使得集合中邊的權(quán)值之和最大或最小。而二分圖的最佳匹配則一定為完備匹配，在此基礎(chǔ)上，才要求匹配的邊權(quán)值之和最大或最小。二分圖的帶權(quán)匹配與最佳匹配不等價(jià)，也不互相包含。 我們可以使用KM算法實(shí)現(xiàn)求二分圖的最佳匹配?？梢詤⒖紅ianyi的講解。KM算法可以實(shí)現(xiàn)為O(N^3)。 [KM算法的幾種轉(zhuǎn)化] KM算法是求最大權(quán)完備匹配，如果要求最小權(quán)完備匹配怎么辦？方法很簡(jiǎn)單，只需將所有的邊權(quán)值取其相反數(shù)，求最大權(quán)完備匹配，匹配的值再取相反數(shù)即可。 KM算法的運(yùn)行要求是必須存在一個(gè)完備匹配，如果求一個(gè)最大權(quán)匹配(不一定完備)該如何辦？依然很簡(jiǎn)單，把不存在的邊權(quán)值賦為0。 KM算法求得的最大權(quán)匹配是邊權(quán)值和最大，如果我想要邊權(quán)之積最大，又怎樣轉(zhuǎn)化？還是不難辦到，每條邊權(quán)取自然對(duì)數(shù)，然后求最大和權(quán)匹配，求得的結(jié)果a再算出e^a就是最大積匹配。至于精度問(wèn)題則沒(méi)有更好的辦法了。

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

總結(jié)

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

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