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