ЛКШ 2018, 6-й день, Потоки-2 (Сергей Копелиович)


  1. Разбор
    1. Global cut − перебирать можно только одну вершину
    2. Геом − задача про касательные

  2. Диниц
    1. С прошлой пары: декомпозиция на пути и циклы за O(VE)
    2. Идея улучшения Эдмондса-Карпа, реализация за O(V2E)
    3. Реализация с масштабированием, доказательство времени O(VElogU)
    4. Реализация без масштабирования, но с link-cut за O(VElogV)
    5. Теорема Карзанова, время работы Диница O(EC1/2)
    6. Применение Каразанова: единичные сети → E3/2, паросочетание → EV1/2

  3. Mincost flows
    1. Mincost k-flow за O(k * Поиск пути). Поиск пути = Форд-Беллман
    2. Поиск пути = Дейкстра с потенциалами
    3. Mincost circulation, Алгоритм Клейна (толкаем по отрицательным циклам)
    4. Mincost k-flow → mincost circulation
    5. Mincost flow, 2 способа: бинпоиск и mincost circulation, итеративный поиск путей
    6. Capacity scaling O(E2logU) для mincost circulation

  4. Задачи
    1. Совершенный парсоч, в котором минимальное ребро максимально (есть решение за V3logE и V3)
    2. k непересекающихся возрастающих подпоследовательностей максимальной суммарной длины
    3. mincost LR-flow

  5. С прошлой пары
    1. Минимальное вершинное покрытие за O(VE)
    2. Вершинное покрытие минимального веса за O(flow)

  6. [skipped] Дополнительно: Глобальный разрез за O(V2log2) − Каргер-Штейн

  7. [skipped] Дополнительно, если успеем: попытка рассказать быстрый крутой поток
    1. [skipped] Название preflow push-relabel with global relabeling
    2. [skipped] Толкнуть жадно по всем рёбрам из истока capacity[s,v]
    3. [skipped] bfs от стока по обратным не насыщенным рёбрам
    4. [skipped] Пройти сверху вниз, толкнуть по всем рёбрам вниз столько, сколько можем
    5. [skipped] Если ничего не толкнулись перешли в фазу "толкать в исток, а не сток"