Задачка на подумать из практики

[g.Naukovych]

Я решил эту задачу алгоритмом поиска максимального потока.

Общее решение таково.
У нас есть 1 вершина - неограниченный источник баллов.
есть вершины - группы баллов.
от первой вершины до каждой вершины группы баллов протягиваем ребро (трубу).
пропускная способность каждой трубы равна сумме доступных баллов для группы.

Далее у нас есть вершины - позиции.
Если эту групу баллов можно потратить на эту позицию, то соединяем вершины ребром (трубой)
Пропускная способность ребра устанавливается как бесконечность (очень большое число)
далее создаем еще одну вершину (сток).
соединяем вершины позиций с вершиной сток. пропускная способность каждого ребра (трубы) равна стоимости позиции.
теперь у нас система труб. Пускаем воду в эту систему и понимаем сколько по какой трубе течет.
Отсюда можно понять, сколько какой группы баллов будет тратиться.

[S.Kuskov]

По-моему, при такой схеме первыми будут расходоваться группы с большим количеством балов, и не факт что это будут более уникальные группы. Разве нет?

[Diman]

Цитата:

Сообщение от g.Naukovych

Я решил эту задачу алгоритмом поиска максимального потока.
.

Тоже вариант.