Паросочетание в произвольном графе (15-е мая 2019)

  1. Псевдокод Габова за O(n3)
    1. mate[], p[], восстановление пути.
    2. Инициализация bfs, тело bfs, случаи петля, 1→2, 1→1
    3. Случай 1→1, сжатие цикла: b = LCA(v,x); go(v,x,b); go(x,v,b); if mark[base[i]] then mark[base[i]] := b.
    4. Пишем go(v,x,b) (картинка, где видно, что идти нужно до b1, b2, но не дальше)
    5. Картинка "сжатие уже сжатых циклов"

  2. Оптимизации
    1. Не обнулять пометки в Куне: V3 → |M|V2
    2. Жадная инициализация: нашли паросочетание размера ≥ |M|/2, соптимизили предыдущее в ≥ 2 раз
    3. Прикрутить DSU, чтобы дойти до O(nmα) - главное искать LCA за O(k) и сжимать цикл за O(k), расставлять p[] быстрее "пройти по пути" так и не научились

  3. Двойственность в LP
    1. Построение двойственных задач для Ax = b, x ≥ 0 | Ax ≤ b | Ax ≤ b, x ≥ 0
    2. Слабая и сильная теоремы двойственности
    3. Доказательство сильной теоремы двойственности: симплекс метод корректен и таскает за собой решения и прямой, и двойственной задач