Mincost потоки (21 апреля 2016)

1. Задачи
1. Транспортная задача
2. Найти паросочетания минимального/максимального веса в двудольном графе (задача о назначениях)
3. Хранение неориенртированного графа
4. Проверить поток на минимальность стоимости
5. Найти mincost циркуляцию
6. Свести задачу "mincost поток фиксированного размера" к задаче "mincost циркуляция"
7. Найти mincost flow (размер потока при этом не фиксированный, а произвольный)
8. Выделение k непересекающихся возрастающих подпоследовательностей максимальной суммарной длины за O(E + kV²) = O(kn²).
9. Найти LR-поток через один запуска mincost потока
10. Найти LR-поток минимальной стоимости
2. Кодим
1. Mincost flow Форд-Беллманом [code]
3. Дополнительные задачи
1. Величина потока в планарном гране между двумя вершинами, лежащих на внешней гране
2. Есть k автоматов и n заданий. Про каждое задание известно, во сколько его нужно начать делать, во сколько закончить, а также его стоимость. Каждый автомат может выполнять только одно задание в каждый момент времени. Нужно выполнить задания максимальной суммарной стоимости. Решение за O(kn log n).