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

  1. [Сережа.K] Конец предыдущей лекции
    1. [L,R]-поток
    2. максимальный [L,R]-поток
    3. Лемма про то, что после bfs расстояния только растут
  2. [Сережа.K] Немного теории
    1. Лемма Холла
    2. Существование совершенного паросочетания в двудольном регулярном графе
    3. Дополнение графа до регулярного
    4. Разбиение графа на паросочетания
    5. Покраска ребр двудольного графа в минимальное число цветов
  3. [Сережа.K] MinCost
    1. O(|f|×MinPath)
    2. Доказательство корректности (рассмотрели разность k+1 и k)
    3. Отрицательные циклы. Как их искать, что с ними делать?
    4. Форд-Беллман (обычный, с очередью, Левит)
    5. Дейкстра и потенциалы
    6. Реализации Дейкстры: set, куча, k-ичная куча, дерево отрезков
    7. Случай ориентированного (2E ребер) и неориентированного графа (4E ребер)
  4. [Сережа.K] Задачи. Часть два.
    1. [skipped] [LR-flow] Округление матрицы
    2. [flow] Ориентация графа
    3. [flow] Поиск цикла через s и t в неор графе, в ор графе (NP-Hard)
    4. [flow] Люди (отрезок времени) и самолеты (вместимость)
    5. [matching] K автоматов, выполнить i-заказ = занять один из автоматов в отрезок [Li..Ri]
    6. [skipped] [cut] Удаление графа за минимальную стоимость (in_delete_cost, out_delete_cost)
    7. [mincost flow] Паросочетание минимального веса в двудольном графе
    8. [skipped] [mincost flow] K автоматов, у каждого заказа есть стоимость (построим два графа, в одном много ребер, в другом мало)
    9. [skipped] [cut] Работы и инструменты
    10. [skipped] [cut] Поиск подграфа максимальной плотности в неор графе
    11. [skipped] [cut] Матан (поиск замкнутого подграфа в орграфе максимального веса)
  5. [skipped] [Сережа.K] Алгоритм Диница
    1. [skipped] Сеть кратчайших путей
    2. [skipped] Поиск пути за O(V) и удаление лишних ребер
    3. [skipped] Доказательство времени работы O(V2E)
    4. [skipped] Скрещивание с масштабированием: O(VElogU)
    5. [skipped] Хопкрофт-Карп