## ЛКШ 2018, 6-й день, Потоки-2 (Сергей Копелиович)

1. Разбор

1. Global cut − перебирать можно только одну вершину
2. Геом − задача про касательные

2. Диниц

1. С прошлой пары: декомпозиция на пути и циклы за O(VE)
2. Идея улучшения Эдмондса-Карпа, реализация за O(V2E)
3. Реализация с масштабированием, доказательство времени O(VElogU)
4. Реализация без масштабирования, но с link-cut за O(VElogV)
5. Теорема Карзанова, время работы Диница O(EC1/2)
6. Применение Каразанова: единичные сети → E3/2, паросочетание → EV1/2

3. Mincost flows

1. Mincost k-flow за O(k * Поиск пути). Поиск пути = Форд-Беллман
2. Поиск пути = Дейкстра с потенциалами
3. Mincost circulation, Алгоритм Клейна (толкаем по отрицательным циклам)
4. Mincost k-flow → mincost circulation
5. Mincost flow, 2 способа: бинпоиск и mincost circulation, итеративный поиск путей
6. Capacity scaling O(E2logU) для mincost circulation

4. Задачи

1. Совершенный парсоч, в котором минимальное ребро максимально (есть решение за V3logE и V3)
2. k непересекающихся возрастающих подпоследовательностей максимальной суммарной длины
3. mincost LR-flow

5. С прошлой пары

1. Минимальное вершинное покрытие за O(VE)
2. Вершинное покрытие минимального веса за O(flow)

6. [skipped] Дополнительно: Глобальный разрез за O(V2log2) − Каргер-Штейн
7. [skipped] Дополнительно, если успеем: попытка рассказать быстрый крутой поток

1. [skipped] Название preflow push-relabel with global relabeling
2. [skipped] Толкнуть жадно по всем рёбрам из истока capacity[s,v]
3. [skipped] bfs от стока по обратным не насыщенным рёбрам
4. [skipped] Пройти сверху вниз, толкнуть по всем рёбрам вниз столько, сколько можем
5. [skipped] Если ничего не толкнулись перешли в фазу "толкать в исток, а не сток"