Методы применения алгоритма нахождения максимального потока в сети

[inspush]

торт!

[red1ynx]

Спасибо, интересно.
Только лучше использовать специализированные алгоритмы. Например, для паросочетаний тот же Кун работает за O(n^2), когда max-flow за O(n^3).

[AlMag]

Ну, этим можно пользоваться, когда у Вас уже накожен поток и ограничения позволяют его пустить. Тогда только исток и сток добавить. Экономия времени.

Например, для паросочетаний тот же Кун работает за O(n^2)

O(N*M) точнее. Плюс эвристики позволяют хорошо сэкономить на случайных графах

[EgorK]

В посте по ссылке какой-то очень сложный алгоритм потока представлен. На олимпиадах обычно используется алгоритм попроще, который работает за O(E * F), где F — число раз, которые мы находим новый путь из истока в сток (в случае, если все ребра имеют пропускную способность 0 или 1 — это просто максимальный поток). В большинстве случаев он опережает остальные алгоритмы по скорости

[AlMag]

если писать чистого Форда-Фалкерсона, то он может по времени не пройти на некоторых тестах (с большим весом ребер). По ссылке сразу реализован максимальный поток минимальной стоимости.
Здесь в разделе «потоки и связанные с ними задачи» можно разобраться с большинством существующих методов пускания потока.

[red1ynx]

А сайт по ссылке ваш?

[AlMag]

нет, это многоуважаемого e-maxx

[tagir_valeev]

У задачи минимального разреза есть очень интересное применение — сшивка текстур.
Тут статья с SIGGRAPH и куча картинок и видюшек по теме:
www.cc.gatech.edu/cpl/projects/graphcuttextures/

[vicnaum]

Класс.

Склейка панорам в фотошопе по ходу по такому же алгоритму работает (с четкими границами, Seams). Да и не только в нём.

[tagir_valeev]

Кстати, если кому-то потребуется этот алгоритм в реальной жизни, горячо рекомендую реализацию Юрия Бойкова и Владимира Колмогорова. Качать тут:
vision.csd.uwo.ca/code/ (бесплатно для некоммерческого использования).

[AlMag]

Бросайте линк. Кто захочет — возьмет для себя что-то новое.

[MRoizner]

Спасибо за пост, очень понравилось.
+ в карму

Круто было бы, если бы Вы ещё смогли собрать такой же набор на mincost…

[AlMag]

да, спасибо, работаю в этом направлении. Пост будет ближе к началу сентября