ЛКШ 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. Дополненительно: пример, на котором Ф.Ф, работает экспоненту от V