Ходят слухи, что min-cost-max-flow пишется за асимптотику n^3, а не n*m^2*logn. Верно ли это? Гугл не дает никакой информации по такому запросу. Подскажите пожалуйста настоящую асимптотику алгоритма и дайте ссылку на реализацию.
Ходят слухи, что min-cost-max-flow пишется за асимптотику n^3, а не n*m^2*logn. Верно ли это? Гугл не дает никакой информации по такому запросу. Подскажите пожалуйста настоящую асимптотику алгоритма и дайте ссылку на реализацию.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Если я не ошибаюсь, он работает за 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)