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

1. Что мы уже знаем?
   1. Lm о дополняющем пути (для произвольного графа верна).
   2. Алгоритм Куна и теорема о корректности (двудольностью не пользовались).
   3. dfs/bfs для поиска чередующегося пути.
   4. M₁ xor M₂ (двух паросочетаний), M₁ xor P (паросочетание + путь, чётный или нечётный)
   
   
2. Алгоритм Эдмондса
   1. for v=1..n запустим dfs/bfs(v) от Куна для поиска пути.
   2. Поиск пути нашёл путь или нечётный цикл со стеблем (соцветие = цветок + стебель).
   3. Сожмём нечётный цикл в одну вершину, продолжим поиск. На слове "продолжим" мы понимаем, что из dfs/bfs удобнее bfs.
   4. Корректность: путь ∃ в исходном графе ⇔ путь ∃ в сжатом графе (в одну сторону предъявляем алгоритм расжатия в другую разбираем случаи, как выглядел исходный путь)
   5. Простейшая реализация: создаём новую вершину за O(cycleLen*n), кидаем в очередь, делаем рекурсивный вызов continueBfs, который возвращает путь, если путь проходит через сжатую вершину, делаем расжатие.
   
   
3. Габов: красивая простая реализация алгоритма Эдмондса за O(n³)
   1. mate[], p[], восстановление пути.
   2. Все вершины исходного графа, достижимые как вершины первой доли, образуют дерево по отношению v &arr; p[mate[v]].
   3. Явно сжимать ничего не будем. base[v] = основание цикла, в котором сейчас лежит v, изначально base[v] = v
   4. Сжатие цикла (x,y)
      1. За O(k) находим b=LCA(x,y) в v → p[mate[v]].
      2. Проходим части пути x → first x₁ : base[x₁] = b и y → first y₁ : base[y₁] = b, проставляем новые ссылки p[], добавляем вершины в очередь, ∀ t на пути помечаем mark[base[t]]=true.
      3. За O(n) перебираем все вершины i и: if mark[base[i]] then mark[base[i]] := b.
      4. Корректность обновления ссылок: путь x &rarr x₁ и y → y₁ не пересекаются по вершинам ⇒ рассмотрим нечётный цикл y₁-y-x-x₁, ото всех вершин мы по ссылкам теперь можем дойти до v: base[v]=b, а от v точно можем дойти до b (т.к. ссылки от w: base[w]=b не меняли).
      5. Почему нельзя идти до b? Тогда пути могли бы пересекаться и ссылки зациклятся (сместим x₁ и y₁ на цикле по чётности, куски пути x₁ → b и y₁ → b будут пересекаться)
      6. Картинка "сжатие уже сжатых циклов" (цикл циклов)
   
   
4. Оптимизации базовой реализации за V³
   1. Не обнулять пометки в Куне: V³ → |M|V²
   2. Жадная инициализация: нашли паросочетание размера ≥ |M|/2, соптимизили предыдущее в ≥ 2 раз
   3. Прикрутить DSU, чтобы дойти до O(nmα)
      1. LCA можно искать за O(kα), а можно писать dfs и получать LCA за O(1)
      2. Сжимать цикл можно за O(kα) (v → p[getBase(v)])
      3. Расставлять новые p[] быстрее не умеем: нам недостаточно вершины getBase(v), нам нужна ещё и предыдущая. Но для определения "есть ли путь" p[] от внутренних вершин цикла и не нужны, нужно только поддерживать p[base].
      4. Если хотим восстановить путь, можно это делать не благодаря p[], а уже в конце.
   
   
5. Задача: поиск минимального по весу простого чётного пути.