Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.08.2008, 13:21
гость

 
Сообщений: n/a

Максимальный поток
Здравствуйте!
Короче задача такая: имееться сеть, исток и каждая вершина по очереди должна побывать стоком (ну или соединена со стоком) и соответственно каждый раз нужно найти макс. поток. Каждый раз я заново нахожу максимальный поток, но это слишком медленно. Вроде где то слышал что можно сначала найти поток , а потом поменять сток и при этом полностью не перестраивая поток можно снова искать.
Подскажите пожайлуста есть ли такой метод или какието другие упрощения?
  #2  
Старый 31.08.2008, 06:45
Аватар для Schemer
Пользователь

Отправить личное сообщение для Schemer Посмотреть профиль Найти все сообщения от Schemer
 
Регистрация: 26.07.2008
Адрес: Moscow
Сообщений: 93

I think it's called 'Gomory-Hu method'.

If you're just looking for a global min-cut of an undirected graph (i.e. you're not really interested in non-minimum cuts), then there are simpler and faster non-maxflow-based solutions: for example Stoer-Wagner's algorithm, and Karger's algorithm.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Максимальный поток в сети гость Графы 5 25.05.2010 00:43
максимальный поток в графе с использованием параллельных вычислений kernel1987 Графы 0 19.04.2008 21:22
Максимальный поток MrFandorin Графы 3 14.04.2008 13:53
максимальный поток\ "задача о ресурсах" ExPerT Реализация, исходники, языки 0 27.03.2007 14:08
задачи на максимальный поток Olegator Задачи 5 02.11.2006 13:35