| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Максимальный поток |
| Автор: MSDN 27.8.2008, 12:20 |
| Здравствуйте! Короче задача такая: имееться сеть, исток и каждая вершина по очереди должна побывать стоком (ну или соединена со стоком) и соответственно каждый раз нужно найти макс. поток. Каждый раз я заново нахожу максимальный поток, но это слишком медленно. Вроде где то слышал что можно сначала найти поток , а потом поменять сток и при этом полностью не перестраивая поток можно снова искать. Подскажите пожайлуста есть ли такой метод или какието другие упрощения? |
| Автор: tab 1.10.2008, 01:07 | ||
| Идейно можно двигаться вот в каком направлении: максимальный поток в графе равен минимальному разрезу. Перемещая только сток в соседнюю вершину, набор вершин составляющий минимальный разрез может измениться, но не сильно. Таким образом для стока в соседней вершине нам нужно сделать довольно небольшой, локальный, перебор, а не решать все заново.Тебя как я понимаю интересует только число, а не весь граф? И еще - не понял фразу:
Быть и быть соединенной вообще говоря вещи разные. |