Задача King and Roads
Даны пары чисел(упррядоченные), каждое от 1 до n. Всего m штук. У каждой пары есть стоимость.
Надо выбрать сколько-нибудь пар чисел, так, чтобы :
Для каждого числа i от 1 до n должна существовать выбранная пара, такая что ее левое (правое) число равно i;
Тоесть все левые числа покрывают множество 1..n и тоже с правыми.
Надо минимизировать сумму всех выбранных пар.
n < 300; m < 300 * 300;
Можно уточнить условие? Почему нельзя взять все пары? Нужно минимизировать количество пар или нужно, чтобы слева/справа не было повторений?
ой, извиняюсь.
Надо минимизировать стоимость выбора всех пар.
Определим degL(i) = количество пар, где i слева, аналогично degR(i).
Построим сеть исток — левые числа (n вершин) — правые числа (тоже n) — сток. Из истока в левую вершину пропускная способность degL(i) - 1 (аналогично из правых в сток). Между левыми и правыми рёбра, соответствующие парам в инпуте, только стоимость со знаком минус. Найдём минкост. А те рёбра, что в итоге не насыщены потоком — ответ.
Только поток нужен не максимальный. По всем потокам нужен минимальной стоимости. Это можно делать, проталкивая каждый раз 1 потока. Это может на ассимптотику повлиять, я не шарю.
Вот такая же задач, только с меньшими ограничениями, я её так и решал.
Круто, я понял)
Спасибо большое!
Казалось бы, можно пропихивать всегда много потока, просто нужно перестать это делать, когда стоимость будет положительной.
Кстати, была тут одна тема, давным-давно на СF...