Предистория↵
--------↵
Недавно писал решение на свою задачу _(ниже приложен мэшап, где она находится)_. Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным _(а также я не знаю как строго доказывать такую скорость)_ и поэтому я решил написать этот пост.↵
↵
Краткая формулировка задачи↵
---------------------------↵
Дан ориентированный граф на $n$ вершинах и $m$ ребрах, нужно разбить граф на минимальное количество путей. Особенностью данного графа является то, что его диаметр $^\dagger$ можно оценить как $O(log(n))$.↵
↵
$^\dagger$ Диаметром графа называется максимальное кратчайшее расстояние среди всех пар вершин.↵
↵
Решение↵
-------↵
↵
Очевидно, что данная задача является учебной — нужно дублировать вершины и провести ребра графа в новом двудольном графе. Ответом будет $n - x$, где $x$ — максимальное паросочетание в получившемся двудольном графе.↵
↵
Я приложу свой код алгоритма Куна, который содержит несколько оптимизаций.↵
↵
↵
~~~~~↵
int used[N];↵
int mt[N], timer = 1;↵
vector <int> g[N];↵
bool dfs (int u) {↵
if (used[u] == timer) return false;↵
used[u] = timer;↵
for (int v: g[u]) {↵
if (mt[v] == -1) {↵
mt[v] = u;↵
return true;↵
}↵
}↵
for (int v: g[u]) {↵
if (dfs(mt[v])) {↵
mt[v] = u;↵
return true;↵
}↵
}↵
return false;↵
}↵
// ...↵
int main () {↵
// ...↵
for (int i = 0; i < n; ++i) {↵
dfs(i);↵
timer++;↵
}↵
// ...↵
}↵
~~~~~↵
↵
#### Оптимизации:↵
↵
- Хранение в массиве used значение timer'а, а не зануление used'ов каждый раз↵
↵
- При запуске сначала ищем свободную вершину во второй доле, а потом ищем удлиняющую цепочку.↵
↵
Почему так быстро?↵
------------------↵
Казалось бы, при ограничениях $n = 10^5, m = 10^6$ Кун будет работать $O(n \cdot m)$, что очень долго. Но на реальном графе Кун работает ~$100$ мс.↵
↵
Лично я не знаю, как доказывать такую асимптотику, но моя гипотеза, что у Куна есть ограничение на количество проделанных операций. И данное ограничение можно оценить как $O((n + m) \cdot d)$, где $d$ — диаметр графа.↵
↵
Вот [ссылка](https://mirror.codeforces.com/contestInvitation/0937670bdc4ba5bf948e7dc06dc2c9dfe5ea5c28) на мэшап, где можно протестировать Куна.↵
↵
Интересно услышать ваше мнение насчёт данной гипотезы.
--------↵
Недавно писал решение на свою задачу _(ниже приложен мэшап, где она находится)_. Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным _(а также я не знаю как строго доказывать такую скорость)_ и поэтому я решил написать этот пост.↵
↵
Краткая формулировка задачи↵
---------------------------↵
Дан ориентированный граф на $n$ вершинах и $m$ ребрах, нужно разбить граф на минимальное количество путей. Особенностью данного графа является то, что его диаметр $^\dagger$ можно оценить как $O(log(n))$.↵
↵
$^\dagger$ Диаметром графа называется максимальное кратчайшее расстояние среди всех пар вершин.↵
↵
Решение↵
-------↵
↵
Очевидно, что данная задача является учебной — нужно дублировать вершины и провести ребра графа в новом двудольном графе. Ответом будет $n - x$, где $x$ — максимальное паросочетание в получившемся двудольном графе.↵
↵
Я приложу свой код алгоритма Куна, который содержит несколько оптимизаций.↵
↵
↵
~~~~~↵
int used[N];↵
int mt[N], timer = 1;↵
vector <int> g[N];↵
bool dfs (int u) {↵
if (used[u] == timer) return false;↵
used[u] = timer;↵
for (int v: g[u]) {↵
if (mt[v] == -1) {↵
mt[v] = u;↵
return true;↵
}↵
}↵
for (int v: g[u]) {↵
if (dfs(mt[v])) {↵
mt[v] = u;↵
return true;↵
}↵
}↵
return false;↵
}↵
// ...↵
int main () {↵
// ...↵
for (int i = 0; i < n; ++i) {↵
dfs(i);↵
timer++;↵
}↵
// ...↵
}↵
~~~~~↵
↵
#### Оптимизации:↵
↵
- Хранение в массиве used значение timer'а, а не зануление used'ов каждый раз↵
↵
- При запуске сначала ищем свободную вершину во второй доле, а потом ищем удлиняющую цепочку.↵
↵
Почему так быстро?↵
------------------↵
Казалось бы, при ограничениях $n = 10^5, m = 10^6$ Кун будет работать $O(n \cdot m)$, что очень долго. Но на реальном графе Кун работает ~$100$ мс.↵
↵
Лично я не знаю, как доказывать такую асимптотику, но моя гипотеза, что у Куна есть ограничение на количество проделанных операций. И данное ограничение можно оценить как $O((n + m) \cdot d)$, где $d$ — диаметр графа.↵
↵
Вот [ссылка](https://mirror.codeforces.com/contestInvitation/0937670bdc4ba5bf948e7dc06dc2c9dfe5ea5c28) на мэшап, где можно протестировать Куна.↵
↵
Интересно услышать ваше мнение насчёт данной гипотезы.
