День 8. Потоки.
- [Сергей Копелиович] C++: bitset
- [Олег Давыдов] Потоки
- Определение потока (f) в общем случае. 0 ≤ f ≤ c. Сумма f для каждой вершины = 0. f[e] = -f[e']
- Два непересекающихся по ребрам пути − поток. k непересекающихся по ребрам пути − поток.
- Определение циркуляции. Примеры: цикл, два пересекающихся цикла.
- Разрез (определение = дизъюнктное разбиение множества вершина). min Cut ≥ max Flow.
- Теорема и алгоритм Форда Фалкерсона поиска потока за O(|f| × E)
- Декомпозиция потока (разбиение на пути и циркуляцию) за O(E2). За O(VE).
- [Олег Давыдов] Хранение графа
vector<Edge> c[n]
, тогда Edge = {from, to, f, c, rev}
, тогда обратное к "e" ребро − c[to][e.rev]
- Можно
vector<Edge> edges; int head[n]; Edge = {f, c, next};
рёбра добавляются парами: 2i, 2i+1, поэтому переход к обратному − xor 1.
- [Олег Давыдов] Применяем потоки
- Решение задачи о k непересекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
- Непересекающиеся по вершинам пути. Раздвоение вершин.
- Ориентированный граф и неориентированный граф. Два способа представления неориентированного.
- Нахождение паросочетания в двудольном графе с помощью потока за O(VE).
- Несколько истоков и стоков
- [Олег Давыдов] Алгоритмы поиска потока
- Общая идея #1: проталкивать максимально много = mine(ce - fe)
- Эдмондс-Карп (bfs, VE2 = E × VE). А еще он работает на вещественных пропускных способностях.
- Корректность Эдмоднса-Карпа: расстояния d[s,v] только растут
- Масштабирование, оно же Scaling (на k-й фазе толкаем 2k, время E2logU, а в реальности даже E2)
- Корректность масштабирования: после предыдущей фазы есть разрез, где все рёбра <2k+1 ⇒ не более E путей размера 2k
- [Олег Давыдов] Задачи
- Выделение k-регулярного рёберного подграфа из двудольного (определок: совершенное паросочетание, регулярность)
- Восстановление матрицы (есть суммы строк и столбцов, каждое число от 0 до 100)
- Турнирная таблица (нужно доиграть несыгранные матчи, чтобы получились нужные суммы очков)