Тема: MinCostFlow
Здравствуйте!
Я вот тут изучил эту штуку замечательную... Решил пару задач, с тимуса про фараонов по моему...
Народ пожалуйста киньте ссылок на задачи на эту тему... Так сказать чтоб закрепить 
Re: MinCostFlow
Знаю про bacs.cs.istu.ru задача 2097, можно MCF решить
Re: MinCostFlow
Re: MinCostFlow
По поводу http://acm.tju.edu.cn/toj/showp3502.html
Мне кажется это больше похоже на бфс по состояниям, чем на минкост.... Для минкоста ограничения большие получаются.... Или может я не так решаю задачу?
Как бы в самом поганом случае получается N*N/2 вершин, то есть 450, для минкоста многовато. Я думал над тем чтобы уменьшить число вершин скажем представлять вершину как пересечение строки и столбца - но чего то так и не придумал ничего путнего....
Re: MinCostFlow
MSDN пишет:
По поводу http://acm.tju.edu.cn/toj/showp3502.html
Мне кажется это больше похоже на бфс по состояниям, чем на минкост.... Для минкоста ограничения большие получаются.... Или может я не так решаю задачу?
Как бы в самом поганом случае получается N*N/2 вершин, то есть 450, для минкоста многовато. Я думал над тем чтобы уменьшить число вершин скажем представлять вершину как пересечение строки и столбца - но чего то так и не придумал ничего путнего....
Да нет, по моему как раз нормальное количество вершин. Дело в том, что в задачах на поток не стоит смотреть на сложность работы алгоритма в худшем случае, потому что обычно графы в задачах имеют не общий вид. Кстати, в этой задаче (как и в многих других на MCMF) можно использовать венгерский алгоритм. Сложность его работы O(N^3), но константа небольшая, поэтому порой он и для 1000 вершин в каждой доле работает достаточно быстро.
Re: MinCostFlow
Если кому еще интересно, вот прикольная задача: http://acmicpc-live-archive.uva.es/nuev … php?p=4263 Особенно замечательно то, что TL на ней аж 120 сек 
8 2010-10-01 14:18:56 Отредактировано mincer (2010-10-04 04:21:39)
Re: MinCostFlow
А как решать http://acm.tju.edu.cn/toj/showp3492.html
Я так пробовал: представляем все отрезки в виде пары вершин (вход, выход), между которыми ребро с проп. способностью 1 и стоимостью -ci. Между выходом отрезка i и входом отрезка j есть ребро если aj >= bi. Ставим ребра из истока в входы всех отрезков, и из выходов всех отрезков в сток. Расставляем потенциалы Форд-Беллманом, потом Дийкстрой ищем поток. Имею TL.
Такой подход вообще корректен? Задача вызывает ассоциацию с покрытием путями ориентированного ациклического графа.
Re: MinCostFlow
Никто не подскажет?
Re: MinCostFlow
Такой подход точно не корректен.
Меняй network следующем образом:
1. ужимаешь координаты в набор s = x0 < x1 < x2 < x3 .. xn = t (не больше 400)
2. между xi -> xi+ 1 ребро стоимостью =0, cap = m
3. между x(ai) ->x(bi) ребро стоимостью = -hi, cap = 1
Re: MinCostFlow
Большое спасибо!