День 9. Mincost потоки.
- C++
- templates: struct, function (HashTable, relaxMin)
- templates: частичная специализация (пример с vector<bool>)
- templates: вычисляем n-е число фибоначчи в процессе компиляции
- Mincost поток
- Определение стоимости: ∑ fi wi → min
- Вариации задачи: |f| = 0, |f| = k, |f| = max, ∀ f
- Критерий оптимальности: |f| = k имеет минимальную стоимость ⇔ в сети Gf нет отрицательных циклов
- Решение |f| = 0: пока есть цикл отрицательного веса, добавляем его
- Решение |f| = k, алгоритм Клейна: сперва ищем любой поток |f| = k, потом в Gf решаем ищем циркуляцию min веса (алгоритм Клейна)
- Поиск отрицательных циклов: Форд-Беллман.
- Поиск отрицательного цикла минимального среднего веса за O(VElogM)
- Mincost поток: быстрые алгоритмыt
- Если нам дана циркуляция min веса. Mincost поток размера k = k раз пустить Форд-Беллмана.
- Добавляем потенциалы: k раз пускаем Дейкстру
- Capacity Scaling * E * Dijkstra
- Алгоритм Диниц
- Идея: Эдмондс-Карп ищет VE путей за O(E) каждый, научим его искать пути за O(V)
- Построим сеть кратчайших путей. Утверждение: все пути длины d идут по слоям из s в t. Будем искать все k таких путей за O(E + Vk)
- Итого, время работы: O(V(E + Vki)) = O(VE + V2E)
- Спариваем с масштабированием, тогда очередная фаза масштабирования работает за O(V(E + Vki)) = O(VE + VE)
- Время работы на единичных сетях: O(VE)
- Хопкрофт-Карп = Диниц для поиска паросочетания = O(EV1/2)