Алгоритм на двудольном графе

[B@R5uk]

Подскажите, пожалуйста, как решать следующую задачу.

Имеется двудольных граф. Число вершин справа больше числа вершин слева. Каждая левая вершина соединена как минимум с двумя правыми вершинами (как правило, их пять). Каждая правая вершина соединена как минимум с одной левой вершиной (но их может быть до пяти включительно). Каждая правая вершина имеет вес, а так же ограничение на возможное число выбранных рёбер (обычно один, но величина может быть больше).

Необходимо для левой вершины выбрать в пару одну правую так, чтобы не нарушались ограничения, а сумма весов выбранных вершин была минимальна.

Для начала подошло бы какое-нибудь простое субоптимальное решение. Но честное решение задачи гораздо интереснее. Тут ещё, правда, есть особенность, заключающаяся в том, что веса не совсем случайны, а связаны с устройством графа. Хотелось бы пока обойтись без учёта этого свойства.

[B@R5uk]

Забыл ещё добавить, что у каждой левой вершины графа есть выделенная правая вершина, которую можно назвать зеркальной. На эту правую зеркальную вершину могут претендовать другие левые вершины, но она имеет родство только с одной — отражением которой является. Поэтому у задачи всегда есть решение, когда левые вершины соединены ребром со своим отражением.

-- 17.12.2020, 11:24 --

B@R5uk в сообщении #1496903 писал(а):

веса не совсем случайны, а связаны с устройством графа

Конкретно это выражается в том, что как правило, для каждой левой вершины вес правой, в которую ведёт ребро, либо на единицу больше зеркальной, либо на единицу меньше. Хотя могут быть исключения со значительным скачком.

[mihaild]

B@R5uk в сообщении #1496903 писал(а):

сумма весов выбранных вершин была минимальна

Сумма считается с учетом кратности? То есть если мы одну правую выбрали для двух левых - её вес считается дважды, или один раз?
Если с учетом кратности - то это сводится к потоку минимальной стоимости (почти что он и есть).

[B@R5uk]

С учётом кратности. Но конкретно в моём случае у меня все веса положительны, а у правых вершин, которые допускают несколько выбранных рёбер вес нулевой. Все остальные правые вершины (с ненулевым весом) имеют ограничение в одно выбранное ребро.

mihaild в сообщении #1496912 писал(а):

это сводится к потоку минимальной стоимости

Спасибо! Надо будет вдумываться. Но, если честно, уже страшно.

[B@R5uk]

Так, я, видимо, ошибся. Вес назначается именно ребру, а не вершине, в которую он идёт. То есть в одну вершину могут идти рёбра с разным весом.

[mihaild]

B@R5uk в сообщении #1496927 писал(а):

Вес назначается именно ребру, а не вершине, в которую он идёт

А это уже в чистом виде поток минимальной стоимости с ограничением пропускной способности вершин (которое элементарно сводится к ограничению пропускной способности ребер).

[B@R5uk]

Чёрт! Я забыл одну очень важную вещь. На языке поставленной задачи она заключается в том, что при выборе ребра, ведущего в правую вершину нулевого веса, ведущее в зеркальную вершину ребро тоже резервируется (с нулевым весом). Это ещё одна отличительная особенность зеркальной вершины, и она ломает всю красивую постановку задачи. Теперь я прям вообще в тупике.

[Sender]

Может, на исходном языке сформулируете условие?

[B@R5uk]

Да я на так и сяк кручу задачу о назначениях с хитрыми правилами. Есть несколько работников, каждый из них может быть назначен на некоторое число работ. Для каждого работника это число не больше 5. Число работ больше числа работников и в самом оптимальном случае на работу вообще можно назначить только одного работника В таком случае число работ равно числу рабочих, помноженному на 5. У каждой работы есть цена, целое число от нуля и больше. От обычной задачи о назначениях моя отличается тем, что на некоторые работы можно назначить несколько работников, но не больше заданного числа. А так же тем, что назначение на одну работу (с нулевой ценой) может заблокировать для всех работников назначение на другую работу (зеркальная вершина в предыдущей формулировке). Цена есть только у работ, все работники одинаковые.

Тут ещё есть момент, что цена работ может меняться в зависимости от того, кто куда назначен, но лучше в такие дебри не лезть, выигрыш всё равно будет не большой, а считать ну очень ресурсозатратно.