Задачка с графом

[3DRaven]

Здравствуйте. Есть двудольный граф. G(V1,V2).
Все связи между вершинами V1 V2 взвешены. Задача. Выбрать
Связи такие, чтобы сумма весов была максимальна.
При этом внутри каждого множества вершин связей нет.
Одна вершина множества V1 V2 может быть связана со многими
вершинами другого множества.
Подскажите где искать метод решения. Я нашел для другого типа графов,
поиск кратчайшего пути (аналогично длиннейшего). Но мне надо именно для двудольного и при этом как такового "пути" нет. В результате мы должны получить решение задачи о свадьбах (Холл), но с учетом "максимальных предпочтений". Заранее спасибо.

[maxal]

Уточните условие. Почему нельзя выбрать все ребра (ну или все ребра с положительным весом) - они и дадут максимальную сумму весов.