Maximales Gewicht bipartite Matching

Question

Ich habe ein Diagramm in Form eines rechteckigen Gitters, das heißt N Knoten und Kanten 2N, werden alle benachbarten Knoten verbunden sind. Dies bedeutet, es ist zwei-färbbar, und daher ist es möglich, auf sich bipartiter Anpassung zu tun.

Jede (ungerichtet) Kante hat ein Gewicht ihm zugeordneten - entweder -2, -1, 0, 1 oder 2. Es wird keine andere Werte sind zulässig

Wie würde ich in dieser Grafik gehen über das passende zu finden, die die Summe der Wägungen in der Anpassungs maximiert? Pseudo-Code wäre schön, nicht mit dem speziellen Sprache stören.

Im Idealfall, ich suche für einen Algorithmus, der läuft in quadratischer Zeit -. Vielleicht O (n ^ 2 log n) im schlimmsten Fall

---

Bevor Sie eine Lösung vorschlagen, ich habe versucht, eine maximale Übereinstimmung tut Kanten Gewicht unter Verwendung von 2, dann von Gewicht 1 (ohne Kanten des Gewichts geht über 2). Ich habe 98% bei dieser Implementierung hat (das Problem von einer Informatik ist olympiade) und fragt, was ist die 100% ige Lösung.

Answer 1

Nicht sicher, warum Sie von min Schnitt denken. Ein Schnitt ist in diesem Fall nicht, um Sie passende garantiert. Was Sie tun müssen, ist Zuordnungsproblem zu lösen. Zuordnung Problem . Die aufeinanderfolgenden kürzesten Mathe-Algorithmus löst es in O (EV log V), die in Ihrem Fall ist O (n ^ 2 log n).