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

<br>
# Разбор
## Global cut -- перебирать можно только одну вершину
## Геом -- задача про касательные

<br>
# Диниц
## С прошлой пары: декомпозиция на пути и циклы за O(VE)
## Идея улучшения Эдмондса-Карпа, реализация за O(V^2E)
## Реализация с масштабированием, доказательство времени O(VElogU)
## Реализация без масштабирования, но с link-cut за O(VElogV)
## Теорема Карзанова, время работы Диница O(EC^{1/2})
## Применение Каразанова: единичные сети &rarr; E^{3/2}, паросочетание &rarr; EV^{1/2}

<br>
# Mincost flows
## Mincost k-flow за O(k * Поиск пути). Поиск пути = Форд-Беллман
## Поиск пути = Дейкстра с потенциалами
## Mincost circulation, Алгоритм Клейна (толкаем по отрицательным циклам)
## Mincost k-flow &rarr; mincost circulation
## Mincost flow, 2 способа: бинпоиск и mincost circulation, итеративный поиск путей 
## Capacity scaling O(E^2logU) для mincost circulation

<br>
# Задачи
## Совершенный парсоч, в котором минимальное ребро максимально (есть решение за V^3logE и V^3)
## k непересекающихся возрастающих подпоследовательностей максимальной суммарной длины
## mincost LR-flow

<br>
# С прошлой пары
## Минимальное вершинное покрытие за O(VE)
## Вершинное покрытие минимального веса за O(flow)

<br>
*# Дополнительно: Глобальный разрез за O(V^2log^2) -- Каргер-Штейн

<br>
*# Дополнительно, если успеем: попытка рассказать быстрый крутой поток
*## Название preflow push-relabel with global relabeling
*## Толкнуть жадно по всем рёбрам из истока capacity[s,v]
*## bfs от стока по обратным не насыщенным рёбрам
*## Пройти сверху вниз, толкнуть по всем рёбрам вниз столько, сколько можем
*## Если ничего не толкнулись перешли в фазу "толкать в исток, а не сток"
