Расчет максимального потока в обобщенной сети

Я пытаюсь найти эффективный, общедоступный алгоритм, предпочтительно с реализацией, для решения максимального потока в обобщенной (нечистой) сети с прибылью. Все множители, емкости и значения потока являются ненулевыми целыми числами.Расчет максимального потока в обобщенной сети

Существует ли такой алгоритм или эта проблема не разрешима в полиномиальное время?

источник

2012-05-15 Wander Nauta

Что вы подразумеваете под «нечистым»? В чем недостаток нормальных алгоритмов? –

Дуги могут иметь прирост, т. Е. Количество потока, идущего в дугу, может быть меньше, чем количество вытекающего из него потока. Чистая сеть имела бы только дуги с множителем 1. –

Итак, каждая дуга может иметь другой множитель? или все они будут иметь одинаковый множитель? –

Вот некоторые ссылки на некоторые алгоритмы и некоторые экспликации:

Это мое решение для максимального потока: извините за имя переменных я был молод тогда :) http://infoarena.ro/job_detail/431616?action=view-source
H ope it help

источник

2012-06-13 14:56:12 Mark

Кажется, все это для не обобщенных сетей (т. Е. «Нормальных», где каждый множитель равен 1). –

Расчет максимального потока в обобщенной сети

ответ

Смежные вопросы