$ Потоки. Часть два.

vb = <font color=green>[Ваня]</font>
sk = <font color=darkblue>[Сережа.K]</font>
sm = <font color=darkred>[Сережа.М]</font>

# $sk$ Конец предыдущей лекции
## [L,R]-поток
## максимальный [L,R]-поток
## Лемма про то, что после bfs расстояния только растут

# $sk$ Немного теории
## Лемма Холла
## Существование совершенного паросочетания в двудольном регулярном графе
## Дополнение графа до регулярного
## Разбиение графа на паросочетания
## Покраска ребр двудольного графа в минимальное число цветов

# $sk$ MinCost
## O(|f|&times;MinPath)
## Доказательство корректности (рассмотрели разность k+1 и k)
## Отрицательные циклы. Как их искать, что с ними делать?
## Форд-Беллман (обычный, с очередью, Левит)
## Дейкстра и потенциалы
## Реализации Дейкстры: set, куча, k-ичная куча, дерево отрезков
## Случай ориентированного (2E ребер) и неориентированного графа (4E ребер)

# $sk$ Задачи. Часть два.
!## [LR-flow] Округление матрицы
## [flow] Ориентация графа
## [flow] Поиск цикла через s и t в неор графе, в ор графе (NP-Hard)
## [flow] Люди (отрезок времени) и самолеты (вместимость)
## [matching] K автоматов, выполнить i-заказ = занять один из автоматов в отрезок [L_i..R_i]
!## [cut] Удаление графа за минимальную стоимость (in\_delete\_cost, out\_delete\_cost)
## [mincost flow] Паросочетание минимального веса в двудольном графе
!## [mincost flow] K автоматов, у каждого заказа есть стоимость (построим два графа, в одном много ребер, в другом мало)
!## [cut] Работы и инструменты 
!## [cut] Поиск подграфа максимальной плотности в неор графе
!## [cut] Матан (поиск замкнутого подграфа в орграфе максимального веса)

!# $sk$ Алгоритм Диница
!## Сеть кратчайших путей
!## Поиск пути за O(V) и удаление лишних ребер
!## Доказательство времени работы O(V^2E)
!## Скрещивание с масштабированием: O(VElogU)
!## Хопкрофт-Карп