Алгоритм Куна: различия между версиями
Глеб (обсуждение | вклад) |
|||
(не показано 10 промежуточных версий 2 участников) | |||
Строка 4: | Строка 4: | ||
==Утверждение== | ==Утверждение== | ||
− | Если из вершины $x$ не существует дополняющей цепи относительно паросочетания $M$ и паросочетание $M^{ | + | Если из вершины $x$ не существует дополняющей цепи относительно паросочетания $M$ и паросочетание $M^{\prime}$ получается из $M$ изменением вдоль дополняющей цепи, тогда из $x$ не существует дополняющей цепи в $M^{\prime}$. |
==Следствие== | ==Следствие== | ||
Строка 17: | Строка 17: | ||
if (used[v]) { | if (used[v]) { | ||
return false; | return false; | ||
− | + | } | |
− | + | used[v] = true; | |
− | + | for (auto to : g[v]) { | |
− | + | if (mt[to] == -1 || dfs(mt[to])) { | |
− | + | mt[to] = v; | |
− | + | return true; | |
+ | } | ||
} | } | ||
return false; | return false; | ||
Строка 31: | Строка 32: | ||
==Асимптотика== | ==Асимптотика== | ||
− | + | Обозначим размер левой доли $N$, правой ~- $M$, а число рёбер ~- $E$. | |
− | Мы запускаем DFS из всех вершин, то | + | Мы запускаем DFS из всех вершин левой доли, то итоговая асимптотика - $O(N \cdot (\underbrace{N + M}_{\text{всего вершин}} + E))$. Из этой формулы в частности видно, что в качестве левой доли стоит брать долю, в которой число вершин минимальное из двух долей. |
==Оптимизации== | ==Оптимизации== | ||
Строка 46: | Строка 47: | ||
if (used[v] == now) { | if (used[v] == now) { | ||
return false; | return false; | ||
− | + | } | |
− | + | used[v] = now; | |
− | + | for (auto to : g[v]) { | |
− | + | if (mt[to] == -1 || dfs(mt[to], now)) { | |
− | + | mt[to] = v; | |
− | + | return true; | |
+ | } | ||
} | } | ||
return false; | return false; | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | Подробнее про оптимизации можно почитать [https://codeforces.com/blog/entry/17023?locale=ru здесь]. | ||
==Что дальше== | ==Что дальше== | ||
Строка 62: | Строка 66: | ||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
+ | [[Категория:Конспект]] |
Текущая версия на 16:21, 13 марта 2021
Идея
Мы только, что доказали утверждение о том, что в максимальном паросочетание нет удлиняющих цепей, тогда давайте просто изначально возьмем пустое паросочетание и каждый раз, пока есть удлиняющие цепи будем инвертировать их.
Утверждение
Если из вершины $x$ не существует дополняющей цепи относительно паросочетания $M$ и паросочетание $M^{\prime}$ получается из $M$ изменением вдоль дополняющей цепи, тогда из $x$ не существует дополняющей цепи в $M^{\prime}$.
Следствие
Тогда мы можем найти все удлиняющие цепи, запуская поиск удлиняющей цепи из каждой вершины. Искать удлиняющие цепи мы умеем DFS-ом.
Алгоритм
Давайте пройдемся по всем вершинам первой доли, проверяя насыщена ли текущая вершина(взято ли в паросочетание ребро, инцидентное ей), если насыщена - пропускаем, иначе пробуем насытить следующим DFS-ом:
1 bool dfs (int v) {
2 if (used[v]) {
3 return false;
4 }
5 used[v] = true;
6 for (auto to : g[v]) {
7 if (mt[to] == -1 || dfs(mt[to])) {
8 mt[to] = v;
9 return true;
10 }
11 }
12 return false;
13 }
В DFS-е мы проверяем все ребра из вершины и если есть вершина, которая еще не насыщена, то мы нашли удлиняющую цепь, иначе запустимся и проверим, есть ли удлиняющая цепь и там.
Асимптотика
Обозначим размер левой доли $N$, правой ~- $M$, а число рёбер ~- $E$. Мы запускаем DFS из всех вершин левой доли, то итоговая асимптотика - $O(N \cdot (\underbrace{N + M}_{\text{всего вершин}} + E))$. Из этой формулы в частности видно, что в качестве левой доли стоит брать долю, в которой число вершин минимальное из двух долей.
Оптимизации
Несмотря на достаточно быструю константу(очень часто алгоритм Куна работает настолько быстро, что заходит и при $N = 2e5$, есть несколько его основных оптимизаций :
1) Брать не пустое паросочетание, а например набирать его жадно.
2) Очень часто можно столкнуться с тем, что не все вершины посещаются в DFS и поэтому каждый раз обнулять used - долго и можно просто хранить int в used и проверять что он равен номеру вершины, из которой мы запустили DFS :
1 bool dfs (int v, int now) {
2 if (used[v] == now) {
3 return false;
4 }
5 used[v] = now;
6 for (auto to : g[v]) {
7 if (mt[to] == -1 || dfs(mt[to], now)) {
8 mt[to] = v;
9 return true;
10 }
11 }
12 return false;
13 }
Подробнее про оптимизации можно почитать здесь.
Что дальше
Существует способ искать паросочетания быстрее($E\sqrt{V}$)(Потоки), также существуют способы искать взвешенное паросочетания и паросочетания не в двудольных графах(Сжатие соцветий)
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin