Че-то я почитал решения на 1000 на TopCoder Open Online Round 1 и заметил, что оказывается, многие не умеют писать "не обязательно максимальный поток минимальной стоимости", как в транспортной задаче - то есть когда первичный критерий - минимальной стоимости, а не максимальность потока. Я увидел много решений, где люди перебирали размер потока и запускали несколько mincost maxflow - это же не надо так делать :о
Поэтому думаю кому-то может быть полезно узнать, что чтобы из всех потоков нашелся поток минимальной стоимости, возможно не максимальный, все что нужно - это запускать дийкстру не до победного, а только до тех пор, пока она возвращает отрицательное значение.
Поэтому думаю кому-то может быть полезно узнать, что чтобы из всех потоков нашелся поток минимальной стоимости, возможно не максимальный, все что нужно - это запускать дийкстру не до победного, а только до тех пор, пока она возвращает отрицательное значение.
Но основная идея в том, что каждая дийкстра возвращает значение не меньше чем предыдущая. Значит, если сейчас вернулся ноль или больше, то общая сумма теперь будет исключительно не убывать, и смысла большого продолжать нет.
Это очень важный способ доказывать на ACM-стайл контестах. Выглядит это так:
Тааак, у нас есть задача А. Докажем, что данное утверждение Б верно.
Допустим, что утверждение Б не верно. Тогда я хз, как решить задачу при заданных ограничеиях. Значит, от противного, получает, что ограничение Б верно :о)
По поводу дейкстры - насколько я помню из за отрицательных ребер приходиться писать дейкстру с потенциалами, и поэтому вроде проще использовать алгоритм Левита...
Единственная проблема, которую отрицательные ребра вводят - это необходимость запустить БФ в начале, чтобы заполнить потенциалы.
Здесь написано, почему алгоритм Левита не стоит использовать.
Там написано, почему НЕПРАВИЛЬНЫЙ алгоритм Левита не нужно использовать. А правильный спокойно можно использовать.
Немного некропостинга, дабы не создавать похожую тему.
Задача C VK Cup 2012 Round 3 вызвала у меня некоторые сложности в понимании Дейкстры с потенциалами.
Вопрос такой, чем нужно инициализировать потенциалы, в каких случаях достаточно не инициализировать их совсем.
Меня спасли претест 6 и 7, 6-ой давал ВА, если инициализировать потенциалы нулём. А 7-ой давал ТЛ при инициализации потенциалов беллманом фордом на графе с числом рёбер порядка N^2. В итоге я написал ДП на DAG вместо Беллмана-Форда, и решение зашло.
Если в графе есть отрицательные циклы, то применение дейкстры с потенциалами исключено.
Если нет отрицательных циклов, и перед первым шагом алгоритма нет отрицательных рёбер (или их пропускные способности сейчас нулевые), верно ли что можно инициализировать потенциалы просто нулем?
Да. Ведь все кратчайшие пути неотрицательны.
UPD: это к тому, что в алгоритме все расстояния можно инициализировать нулями.
нужно инициализировать так, чтобы не было отрицательных рёбер, это кажется единственное условие...
Спасибо за пояснения, а то я, полоумный, запускал в таких случаях для инициализации дейкстру, вызывая ту же функцию, что и потом в цикле, но с другим набором параметров.
А можно немного подробнее про потенциалы. Что это такое и почему с ними дейкстра с отрицательными ребрами начинает работать?
Это неплохо описано в Кормене, в параграфе про алгоритм Джонсона.
Вся идея в том, что нужно каждой вершине задать какой-то потенциал, а веса ребер изменить как wφ(uv) = w(uv) + φ(v) - φ(u). И причем веса всех путей между двумя конкретными вершинами изменятся на одинаковое число и кратчайшие пути остануться кратчайшими.
Известно, что потенциал, который сделает все веса неотрицательными, существует тогда и только тогда, когда нет отрицательных циклов. Например, можно взять за потенциалы кратчайшие пути из какой-то вершины, можно убедиться, что все веса будут неотрицательны после введения такого потенциала.
спасибо, почитаю.
А случай отрицательных циклов, как я понимаю, решается сначала нахождением максимального потока произвольной стоимости и, далее, поиском отрицательных циклов и пуском потока по ним, как описано тут ?
Да.
Поток является потоком минимальной стоимости среди всех потоков такой же величины, если в остаточной сети нет отрицательных циклов.
Если отрицательные циклы появятся, то это означает что в вашей сети существует поток стоимости -INF, так что что-то не так.
Неправда. Есть еще пропускные способности, которые ограничивают величину потока.
И правда идея простая, но когда я её в первый раз придумал думать пришлось много