День 9. Mincost потоки.

  1. C++
    1. templates: struct, function (HashTable, relaxMin)
    2. templates: частичная специализация (пример с vector<bool>)
    3. templates: вычисляем n-е число фибоначчи в процессе компиляции

  2. Mincost поток
    1. Определение стоимости: ∑ fi wi → min
    2. Вариации задачи: |f| = 0, |f| = k, |f| = max, ∀ f
    3. Критерий оптимальности: |f| = k имеет минимальную стоимость ⇔ в сети Gf нет отрицательных циклов
    4. Решение |f| = 0: пока есть цикл отрицательного веса, добавляем его
    5. Решение |f| = k, алгоритм Клейна: сперва ищем любой поток |f| = k, потом в Gf решаем ищем циркуляцию min веса (алгоритм Клейна)
    6. Поиск отрицательных циклов: Форд-Беллман.
    7. Поиск отрицательного цикла минимального среднего веса за O(VElogM)

  3. Mincost поток: быстрые алгоритмыt
    1. Если нам дана циркуляция min веса. Mincost поток размера k = k раз пустить Форд-Беллмана.
    2. Добавляем потенциалы: k раз пускаем Дейкстру
    3. Capacity Scaling * E * Dijkstra

  4. Алгоритм Диниц
    1. Идея: Эдмондс-Карп ищет VE путей за O(E) каждый, научим его искать пути за O(V)
    2. Построим сеть кратчайших путей. Утверждение: все пути длины d идут по слоям из s в t. Будем искать все k таких путей за O(E + Vk)
    3. Итого, время работы: O(V(E + Vki)) = O(VE + V2E)
    4. Спариваем с масштабированием, тогда очередная фаза масштабирования работает за O(V(E + Vki)) = O(VE + VE)
    5. Время работы на единичных сетях: O(VE)
    6. Хопкрофт-Карп = Диниц для поиска паросочетания = O(EV1/2)