Потоки-3 (7 апреля)

1. Min Cost Flow - 1
1. Задачи min cost circulation, min cost k-flow, min cost flow, min cost max flow
2. Lm: mincost ⇔ не существует отрицательного цикла в остаточной сети
3. Mincost k-flow = Ребро + Mincost circulation
4. Решение задачи min cost circulation. Алгоритм Клейна: ищем произвольный отрицательный цикл, увеличиваем по нему поток.
5. Решение задачи min cost k-flow в графе без отрицательных циклов. Алгоритм: ищем произвольный путьминимального веса в остаточной сети алгоритмом Форда-Беллмана.
6. Доказательство корректности: разность потоков.
7. Mincost flow: пользуемся леммой ``длина пути растёт'', получаем возрастающую производную функции W(|f|)
1. Последовательный перебор |f|
2. Бинпоиск по ответу
8. Потенциалы и дейкстра. Mincost k-flow за O(FordBellman + k×Dijkstra)
9. [не успеем] Задача о назначениях. Транспортная задача.
2. Min Cost Flow - 2
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=30..0 DO FOR edge DO IF capacity[edge] & 2^k THEN add(edge, 2^k)
2. Как добавить ребро? Если появился отрицательный цикл, он проходит по ребру, найдём его.
3. Время работы = Dijkstra*m*logU
3. [не успеем] Cost Scaling: фаза − уменьшить минимальную стоимость с -С до -С/2 (процесс очень похож на алгоритм Гольдберга)
1. [не успеем] Что мы можем делать, чтобы уменьшить стоимости?
2. [не успеем] Подкрутить потенциалы
3. [не успеем] Толкнуть отрицательный цикл