Интересная гипотеза об асимптотике Куна
Разница между ru4 и ru5, 845 символ(ов) изменены
Предистория↵
--------↵
Недавно писал решение на свою задачу _(ниже приложен мэшап, где она находится)_. Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным _(а также я не знаю как строго доказывать такую скорость)_ и поэтому я решил написать этот пост.↵

Краткая формулировка задачи↵
---------------------------↵
Дан ориентированный граф на $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$ &mdash; диаметр графа.↵

Вот [ссылка](https://mirror.codeforces.com/contestInvitation/0937670bdc4ba5bf948e7dc06dc2c9dfe5ea5c28) на мэшап, где можно протестировать Куна.↵

Интересно услышать ваше мнение насчёт данной гипотезы.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский AndreyPavlov 2023-01-12 10:22:24 845 Мелкая правка: 'n~~~~~\n\nОптимизаци' -> 'n~~~~~\n\n#### Оптимизаци'
ru4 Русский AndreyPavlov 2023-01-12 10:12:54 6 Мелкая правка: 'ть как $O(n \cdot d)$' -> 'ть как $O((n + m) \cdot d)$'
ru3 Русский AndreyPavlov 2023-01-11 21:39:13 2
ru2 Русский AndreyPavlov 2023-01-11 21:36:55 0 (опубликовано)
ru1 Русский AndreyPavlov 2023-01-11 21:36:00 1577 Первая редакция (сохранено в черновиках)