Доброго времени суток Codeforces!
Хочется посабмитить циркуляцию наименьшей стоимости, кто-нибудь помнит задачи на такую тему (или просто на нахождение циркуляции, на нахождение отрицательного цикла, на нахождение кратчайшего отрицательного цикла, отрицательного цикла наименьшего среднего веса).
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
http://mirror.codeforces.com/gym/100199 B — Reactor Cooling
http://mirror.codeforces.com/gym/100491 A — Arbitrage
http://mirror.codeforces.com/gym/100166 D — Кратчайший путь
Спасибо!
Чтобы тестить циркуляцию, достаточно взять любую задачу на min cost flow и решать её как flow + min cost circulation.
Если честно я как раз хочу разобраться с тем за какую асимптотику люди решают циркуляцию наименьшей стоимости. В minCostFlow я конечно могу посабмитить, но скорее всего получу TL.
Почему же не зайдёт? Если циклы минимального среднего веса вычёркиваешь... А если ещё и scaling какой-нибудь делаешь, то очень даже зайдёт =)
Я правильно понимаю в цикле минимального среднего веса мы минимизируем (сумму весов в цикле) / (количество вершин в цикле)? На e-maxxе об этом вскользь упоминается (говорится что можно найти за O(nm), но я пока не знаю как), но реализация похожа на поиск обычного отрицательного цикла. Scaling делается по величине среднего веса?
UPD: Нашел в книге Ахуйи и про минимальный средний вес и про scaling.
Да, правильно.
Алгоритм Карпа за O(VE) гуглится так: "karp minimum mean cycle"
Вот прямая ссылка
Вот обзор про mincost алгоритмы
Вот одна из вариаций на тему cost scaling
Больше гуглится словами: "cost scaling min cost flow"
Удачи ;)
Спасибо
UPD: товарища Ахуйи чаще называют Ахьюджи =) видимо, понятно, почему...
Вопрос немного не по теме: кто-нибудь знает как находить min-cost-flow в сети с нижними ограничениями на пропускные способности?
Я только попробовал найти какой-то поток, потом циркуляцию наименьшей стоимости, но что-то это не взлетело :)
UPD: оказалось, что так и надо делать (под
каким-то потокомимелся в виду макс поток из фиктивного стока в фиктивный исток, он же минимальный поток, удовлетворяющий ограничениям). Значит, надо выправлять руки.Точно также, как и обычный поток: добавляем ребро T->S пропускной способности +Inf, затем каждое ребро a->b с мин. ограничением L, пропускной способности H и стоимости С заменяем на ребра S'->b и a->T' пропускной способности L и одно из них делаем стоимости С, а второе — 0, а самому ребру a->b понижаем пропускную способность до H-L, а стоимость оставляем такую же. Теперь ищем макс поток из S' в T' и проверяем, равен ли он сумме всех минимальных ограничений на ребра. Если не равен, то ответа нет, иначе это и есть min-cost-flow (только важно заметить, что это не min-cost-max-flow).
Спасибо!
Я вроде так и делал, только ещё искал минимальную циркуляцию в сети без S' и T'. Но это не сработало на примере из этой задачи (рисовать, что там не так пока лень :) ).
А на счёт макс потока из S' в T' -- он же ограничен сверху суммой минимальных ограничений, а у нас ещё может быть, допустим, цикл отрицательного веса внутри старой сети, разве нет?
Ну так циклы отрицательного веса на величину потока из S' в T' не влияют.
Не очень понял) А если все минимальные пропускные способности 0, то макс поток из S' в T' будет нулевым потоком стоимости 0 и мы никак не учли min-cost-flow из S в T?
По определению, величина потока из S в T — это сумма потоков по ребрам исходящим из S, она же сумма потоков по ребрам входящим в T. Отрицательные циклы не влияют на величину потока из S в T, при этом они влияют на суммарную стоимость. Чаще всего в задачах, где граф нужно строить самому, отрицательных циклов ненулевой пропускной способности нет (например, в приведенной задаче из acmp), поэтому я о них и не говорил изначально. Конечно, если они есть, то нужно их искать соответствующим алгоритмом.
Ок, ещё раз спасибо)
Надеюсь, последний вопрос -- получается в общем случае всё-таки найти макс поток из S' в T' и потом убирать циклы отрицательного веса?
Да, в общем случае так.