Mincost Потоки (2 октября 2017)

1. Min Cost k-Flow в графе без отрицательных циклов
1. Lm: mincost ⇔ не существует отрицательного цикла в остаточной сети
2. Решение задачи min cost k-flow в графе без отрицательных циклов. Алгоритм: ищем произвольный путь min веса в остаточной сети алгоритмом Форда-Беллмана.
3. Доказательство корректности: разность потоков.
4. Потенциалы и Дейкстра. Mincost k-flow за O(FordBellman + k×Dijkstra)


2. Задачи min cost circulation, min cost k-flow, min cost flow, min cost max flow
1. Mincost k-flow = Flow + Mincost circulation
2. Решение задачи min cost circulation. Алгоритм Клейна: ищем произвольный отрицательный цикл, увеличиваем по нему поток.
3. Mincost flow: пользуемся леммой ``длина пути растёт'', получаем возрастающую производную функции W(|f|)
1. Последовательный перебор |f|
2. Бинпоиск по ответу

1. Min Cost k-Flow: полиномиальное решение
1. Mean cycle canceling: вычёркиваем не произвольный отрицательный цикл, а минимальный по среднему весу.
1. Решение работает за O(nm × min(log(nC),mlogn) × FindCycle)
2. FindCycle можно делать за O(logn), тогда получается алгоритм за O(nmlog(nC)logn)
2. Capacity Scaling для mincost circulation у графа с целочисленными пропускными способностями
1. FOR k=logU..0 DO FOR edge DO IF capacity[edge] & 2^k THEN add(edge, 2^k)
2. Как добавить ребро? Если появился отрицательный цикл, он проходит по ребру, найдём его.
3. Время работы = Dijkstra*m*logU


2. Cost Scaling
1. Фаза − уменьшить минимальную стоимость с -С до -С/2 (процесс очень похож на алгоритм Гольдберга)
2. Что мы можем делать, чтобы уменьшить стоимости? Подкрутить потенциалы и толкнуть отрицательный цикл