Сопоставление максимальных весов с взвешенными вершинами

Question

У меня есть двудольный граф с двумя наборами вершин A и B. Края не имеют весов. Однако вершинам в одном из наборов (скажем, в наборе B) назначены положительные веса (wb1,wb2...). Я хочу найти соответствие в этом двудольном графе, чтобы максимизировать сумму весов вершин, совпадающих с множеством B.

После обширного поиска в Интернете я пришел к следующему: назначить вес wbi всем ребрам, встречающимся в вершине bi, и запустить венгерский алгоритм. Есть ли более эффективный способ взглянуть на эту проблему, так как он отличается от взвешенного максимального соответствия (здесь вершины имеют веса, а не ребра)

Если мой язык не понятен, не стесняйтесь редактировать. Спасибо.

Answer 1

Если улучшение от O(V^3) до O(V E) и более простой алгоритм того стоят (это не асимптотически для самых плотных графов), вы можете использовать структуру соответствия матроидов следующим образом. Создавайте Ford-Fulkerson, многократно выбирая путь к непревзойденной вершине в B, вес которой максимально велик.