## ЛКШ 2018, 5-й день, Потоки (Даня Николенко)

1. База

1. Определения: поток, размер потока, циркуляция, разрез, дополняющий путь. Примеры потоков и дополняющих путей.
2. Теорема и алгоритм ФФ, существование и поиск max-потока в Z-сетях
3. Декомпозиция потока на толстые пути и циклы за O(E2) и за O(VE)
4. Поиск паросочетания, поиск вершинного покрытия
5. Рёберно и вершинно непересекающиеся пути в ор и неор графах
6. Хранение: struct edge { a, b, f, c }

2. Протейшие алгоритмы

1. Эдмодс-Карп (bfs) за O(V2E), существование потока в R-сетях
2. Масштабирование потока за O(E2logU)

3. Немного задач

1. Задача восстановление матрицы: фиксированны суммы в строках, столбцах, расставить значения от 0 до 100
2. Задача про футбольную таблицу: ничей небывает дан недоигранный турнир и желаемое суммарное число побед в конце турнира для каждой команды, восстановить полную таблицу
3. LR-поток : несколько истоков/стоков ; избытки недостатки ; LR-циркуляция ; LR-max-поток
4. Задача про округление матрицы: округлить вещественную матрицу так, чтобы суммы в строках и столбцах изменились меньше чем на 1 (тоже округлились)
5. Задача про вершинное покрытие в двудольном графе минимального веса

4. [skipped] Дополненительно: пример, на котором Ф.Ф, работает экспоненту от V