$ Потоки
vb = [Ваня]
sk = [Сережа.K]
sm = [Сережа.М]
# $vb$ Потоки
## Два неперсекающихся по ребрам пути − поток. k неперсекающихся по ребрам пути − поток.
## Определение потока (f) в общем случае. 0 ≤ f ≤ c. Сумма f для каждой вершины = 0. f[e] = -f[e']
## Разрез. Min Cut ≤ Max Flow.
## Теорема и алгоритм Форда Фалкерсона поиска потока за O(|f| × E)
## Декомпозиция потока (разбиение на пути и циркуляцию) за O(E^2). За O(VE).
## Решение задачи о k неперсекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
## Непересекающиеся по вершинам пути. Раздвоение вершин.
## Ориентированный граф и неориентированный граф. Два способа представления неориентированного.
## Нахождение паросочетания в двудольном графе с помощью потока за O(VE).
# $vb$ Потоковые Фишечки
## Несколько истоков и стоков
## Избытки и недостатки в вершинах
## [L,R]-циркулция (с нижними и верхними ограничениями)
# $vb$ Алгоритмы поиска потока
## Общая идея #1: проталкивать максимум
## Эдмондс-Карп (bfs, VE^2 = E × VE). А еще он работает на вещественных пропускных способностях.
## Масштабирование, оно же Scaling (2^k, E^2logU, а в реальности даже E^2)
# $vb$ Задачи
## [flow] Выделение k-регулярного рёберного подграфа из двудольного (определок: совершенное паросочетание, регулярность)
## [flow] Восстановление матрицы (есть суммы строк и столбцов, каждое число от 0 до 100)
## [flow] Турнирная таблица (нужно доиграть несыгранные матчи, чтобы получились нужные суммы очков)
## [NP-hard] Поиск A-B и C-D путей