Комментарии 14
торт!
Спасибо, интересно.
Только лучше использовать специализированные алгоритмы. Например, для паросочетаний тот же Кун работает за O(n^2), когда max-flow за O(n^3).
Только лучше использовать специализированные алгоритмы. Например, для паросочетаний тот же Кун работает за O(n^2), когда max-flow за O(n^3).
В посте по ссылке какой-то очень сложный алгоритм потока представлен. На олимпиадах обычно используется алгоритм попроще, который работает за O(E * F), где F — число раз, которые мы находим новый путь из истока в сток (в случае, если все ребра имеют пропускную способность 0 или 1 — это просто максимальный поток). В большинстве случаев он опережает остальные алгоритмы по скорости
если писать чистого Форда-Фалкерсона, то он может по времени не пройти на некоторых тестах (с большим весом ребер). По ссылке сразу реализован максимальный поток минимальной стоимости.
Здесь в разделе «потоки и связанные с ними задачи» можно разобраться с большинством существующих методов пускания потока.
Здесь в разделе «потоки и связанные с ними задачи» можно разобраться с большинством существующих методов пускания потока.
У задачи минимального разреза есть очень интересное применение — сшивка текстур.
Тут статья с SIGGRAPH и куча картинок и видюшек по теме:
www.cc.gatech.edu/cpl/projects/graphcuttextures/
Тут статья с SIGGRAPH и куча картинок и видюшек по теме:
www.cc.gatech.edu/cpl/projects/graphcuttextures/
Кстати, если кому-то потребуется этот алгоритм в реальной жизни, горячо рекомендую реализацию Юрия Бойкова и Владимира Колмогорова. Качать тут:
vision.csd.uwo.ca/code/ (бесплатно для некоммерческого использования).
vision.csd.uwo.ca/code/ (бесплатно для некоммерческого использования).
Спасибо за пост, очень понравилось.
+ в карму
Круто было бы, если бы Вы ещё смогли собрать такой же набор на mincost…
+ в карму
Круто было бы, если бы Вы ещё смогли собрать такой же набор на mincost…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Методы применения алгоритма нахождения максимального потока в сети