Ходят слухи, что min-cost-max-flow пишется за асимптотику n^3, а не n*m^2*logn. Верно ли это? Гугл не дает никакой информации по такому запросу. Подскажите пожалуйста настоящую асимптотику алгоритма и дайте ссылку на реализацию.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 6 | adamant | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.11.2024 09:20:21 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Если я не ошибаюсь, он работает за O(N^3) только на единичных сетях.
работает за асимптотику алгоритма нахождения кратчайших путей умножить на величину макс. потока. Источник Может быть есть другие методы нахождения макс потока мин стоимости, но я их не знаю.
Часто величина max flow не превосходит N, а кратчайший путь на графе без отрицательных циклов можно искать за O(N2) алгоритмом Дейкстры. Тогда асимптотика будет как раз O(N3). Например, такая асимптотика верна при нахождении максимального паросочетания минимальной стоимости.
Ходят слухи что за nmlog(nC) книжка Ahuja.
Это с единичными пропускными способностями, с помощью Cost scaling и проталкивания предпотока(push/relabel).
ADD: Ссылка
С единичными пропускными способностями можно в лоб Дейкстрой с потенциалами за O(n * m * log(n)) или O(n^3).
страница 372. конец страницы если использовать динамические деревья то можно получить nmlogn и
. а с wave оптимизацией n3log(nC)