У меня есть график в виде прямоугольной сетки, то есть N узлов и 2N ребер, все смежные узлы соединены.Это означает, что он имеет два цвета, и, следовательно, на нем можно выполнить двустороннее сопоставление.
Каждому (неориентированному) ребру присвоен вес - либо -2, -1, 0, 1, либо 2.Другие значения не допускаются
Как бы я мог найти соответствие на этом графике, которое максимизирует сумму весов в сопоставлении?Псевдокод был бы хорош, не беспокойтесь о конкретных языках.
В идеале, я ищу алгоритм, который работает в квадратичном времени - может быть O (n ^ 2 log n) в худшем случае.
Прежде чем вы предложите решение, я попытался выполнить максимальное совпадение, используя ребра веса 2, а затем веса 1 (не переходя ребра веса 2).Я набрал 98% с этой реализацией (проблема из информатической олимпиады), и мне интересно, что такое 100% решение.