Циркуляции

10 лет назад, # ^ |

Спасибо!

→ Ответить

10 лет назад, # |

Чтобы тестить циркуляцию, достаточно взять любую задачу на min cost flow и решать её как flow + min cost circulation.

→ Ответить

10 лет назад, # ^ |

Если честно я как раз хочу разобраться с тем за какую асимптотику люди решают циркуляцию наименьшей стоимости. В minCostFlow я конечно могу посабмитить, но скорее всего получу TL.

→ Ответить

10 лет назад, # ^ |

Почему же не зайдёт? Если циклы минимального среднего веса вычёркиваешь... А если ещё и scaling какой-нибудь делаешь, то очень даже зайдёт =)

→ Ответить

10 лет назад, # ^ |

← Rev. 3 →

Я правильно понимаю в цикле минимального среднего веса мы минимизируем (сумму весов в цикле) / (количество вершин в цикле)? На e-maxxе об этом вскользь упоминается (говорится что можно найти за O(nm), но я пока не знаю как), но реализация похожа на поиск обычного отрицательного цикла. Scaling делается по величине среднего веса?

UPD: Нашел в книге Ахуйи и про минимальный средний вес и про scaling.

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

+32

Да, правильно.

Алгоритм Карпа за O(VE) гуглится так: "karp minimum mean cycle"

Вот прямая ссылка

Вот обзор про mincost алгоритмы

Вот одна из вариаций на тему cost scaling

Больше гуглится словами: "cost scaling min cost flow"

Удачи ;)

→ Ответить

10 лет назад, # ^ |

Спасибо

→ Ответить

10 лет назад, # ^ |

+61

UPD: товарища Ахуйи чаще называют Ахьюджи =) видимо, понятно, почему...

→ Ответить

10 лет назад, # |

← Rev. 2 →

Вопрос немного не по теме: кто-нибудь знает как находить min-cost-flow в сети с нижними ограничениями на пропускные способности?

Я только попробовал найти какой-то поток, потом циркуляцию наименьшей стоимости, но что-то это не взлетело :)

UPD: оказалось, что так и надо делать (под каким-то потоком имелся в виду макс поток из фиктивного стока в фиктивный исток, он же минимальный поток, удовлетворяющий ограничениям). Значит, надо выправлять руки.

→ Ответить

10 лет назад, # ^ |

Точно также, как и обычный поток: добавляем ребро 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).

→ Ответить

10 лет назад, # ^ |

Спасибо!

Я вроде так и делал, только ещё искал минимальную циркуляцию в сети без S' и T'. Но это не сработало на примере из этой задачи (рисовать, что там не так пока лень :) ).

А на счёт макс потока из S' в T' -- он же ограничен сверху суммой минимальных ограничений, а у нас ещё может быть, допустим, цикл отрицательного веса внутри старой сети, разве нет?

→ Ответить

10 лет назад, # ^ |

Ну так циклы отрицательного веса на величину потока из S' в T' не влияют.

→ Ответить

10 лет назад, # ^ |

Не очень понял) А если все минимальные пропускные способности 0, то макс поток из S' в T' будет нулевым потоком стоимости 0 и мы никак не учли min-cost-flow из S в T?

→ Ответить

10 лет назад, # ^ |

По определению, величина потока из S в T — это сумма потоков по ребрам исходящим из S, она же сумма потоков по ребрам входящим в T. Отрицательные циклы не влияют на величину потока из S в T, при этом они влияют на суммарную стоимость. Чаще всего в задачах, где граф нужно строить самому, отрицательных циклов ненулевой пропускной способности нет (например, в приведенной задаче из acmp), поэтому я о них и не говорил изначально. Конечно, если они есть, то нужно их искать соответствующим алгоритмом.

→ Ответить

10 лет назад, # ^ |

Ок, ещё раз спасибо)

Надеюсь, последний вопрос -- получается в общем случае всё-таки найти макс поток из S' в T' и потом убирать циклы отрицательного веса?

→ Ответить