最大重量双分匹配

Question

我有一个矩形网格，IE n节点和2N边缘的图形，所有相邻的节点都连接。这意味着它是两种色的，因此可以在其上进行两分匹配。

每个（无方向的）边缘分配了一个重量 - -2，-1、0、1或2。不允许其他值

我将如何找到该图上的匹配，以最大化匹配中称重的总和？伪代码会很好，不要打扰特定的语言。

理想情况下，我正在寻找一种以二次时间运行的算法 - 也许是O（n^2 log n）。

---

在您提出解决方案之前，我尝试使用重量2的边缘进行最大匹配，然后尝试重量1（不超过重量2的边缘）。我在此实施方面得分98％（问题是来自Informatics Olympiad），并且想知道什么是100％的解决方案。

Answer 1

不确定为什么您要考虑砍伐。在这种情况下，不能保证削减可以为您提供匹配。您需要做的是解决分配问题。分配问题. 。连续的最短数学算法在O（eV log V）中求解了它，在您的情况下，它是O（n^2 log n）。