Mincost Потоки (7 октября 2024)

1. Min Cost k-Flow в графе без отрицательных циклов
   1. Lm: mincost ⇔ не существует отрицательного цикла в остаточной сети
   2. Решение задачи min cost k-flow в графе без отрицательных циклов. Алгоритм: ищем произвольный путь min веса в остаточной сети алгоритмом Форда-Беллмана.
   3. Доказательство корректности: разность потоков.
   4. Время работы: O(|f|*FB), O(WVE*FB) для весов 1..W
   5. Потенциалы и Дейкстра. 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. Алгоритм Клейна'67: ищем произвольный отрицательный цикл, увеличиваем по нему поток.
   3. [skipped] [ушло в практику] Mincost flow: пользуемся леммой длина пути растёт, получаем возрастающую производную функции W(|f|)
   4. [skipped] [ушло в практику] Mincost flow: Последовательный перебор |f|, бинпоиск по ответу

1. Mincost circulation и mincost k-flow : быстрые решение
   1. (подробно на практике) Mean cycle canceling (Goldberg, Tarjan'89): вычёркиваем не произвольный отрицательный цикл, а минимальный по среднему весу.
      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
   
   

Доплекция по теме Cost Scaling

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