День 8. Потоки.

  1. [Сергей Копелиович] C++: bitset

  2. [Олег Давыдов] Потоки
    1. Определение потока (f) в общем случае. 0 ≤ f ≤ c. Сумма f для каждой вершины = 0. f[e] = -f[e']
    2. Два непересекающихся по ребрам пути − поток. k непересекающихся по ребрам пути − поток.
    3. Определение циркуляции. Примеры: цикл, два пересекающихся цикла.
    4. Разрез (определение = дизъюнктное разбиение множества вершина). min Cut ≥ max Flow.
    5. Теорема и алгоритм Форда Фалкерсона поиска потока за O(|f| × E)
    6. Декомпозиция потока (разбиение на пути и циркуляцию) за O(E2). За O(VE).

  3. [Олег Давыдов] Хранение графа
    1. vector<Edge> c[n], тогда Edge = {from, to, f, c, rev}, тогда обратное к "e" ребро − c[to][e.rev]
    2. Можно vector<Edge> edges; int head[n]; Edge = {f, c, next}; рёбра добавляются парами: 2i, 2i+1, поэтому переход к обратному − xor 1.

  4. [Олег Давыдов] Применяем потоки
    1. Решение задачи о k непересекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
    2. Непересекающиеся по вершинам пути. Раздвоение вершин.
    3. Ориентированный граф и неориентированный граф. Два способа представления неориентированного.
    4. Нахождение паросочетания в двудольном графе с помощью потока за O(VE).
    5. Несколько истоков и стоков

  5. [Олег Давыдов] Алгоритмы поиска потока
    1. Общая идея #1: проталкивать максимально много = mine(ce - fe)
    2. Эдмондс-Карп (bfs, VE2 = E × VE). А еще он работает на вещественных пропускных способностях.
    3. Корректность Эдмоднса-Карпа: расстояния d[s,v] только растут
    4. Масштабирование, оно же Scaling (на k-й фазе толкаем 2k, время E2logU, а в реальности даже E2)
    5. Корректность масштабирования: после предыдущей фазы есть разрез, где все рёбра <2k+1 ⇒ не более E путей размера 2k

  6. [Олег Давыдов] Задачи
    1. Выделение k-регулярного рёберного подграфа из двудольного (определок: совершенное паросочетание, регулярность)
    2. Восстановление матрицы (есть суммы строк и столбцов, каждое число от 0 до 100)
    3. Турнирная таблица (нужно доиграть несыгранные матчи, чтобы получились нужные суммы очков)