加權二分配匹配

Question

我知道有很多類似的話題。但他們中的大多數在我的情況下給我留下了一些疑問。我想要做的是找到完美的匹配（或者儘可能接近完美，以防萬一沒有完美的匹配），然後從所有匹配中你能匹配k個n個頂點（其中k儘可能高） ），我想選擇儘可能高的總重量。 所以乾脆把我說的是以下優先級：

1. 匹配儘可能多的頂點儘可能
2. 因爲（非加權）在大多數情況下，最大匹配是毫不含糊的，我想選擇有最大的一個邊上的權重總和。如果它們中有幾個具有相同的重量，那麼選擇哪個並不重要。

我聽說過Ford-Fulkerson算法。它是以我描述的方式工作還是需要其他算法？

Answer 1

如果你自己實現這個，你可能想使用Hungarian algorithm。更快的算法存在，但不容易理解或實現。

Ford-Fulkerson是最大流量算法;您可以輕鬆使用它來解決未加權匹配。將其轉化爲加權成熟算法需要額外的技巧;用這個技巧，你用匈牙利算法結束了。

您也可以使用最小成本流算法來進行加權二分配匹配，但它可能不會工作得很好。還有網絡單純形法，但它似乎主要是有歷史意義的。