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

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

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

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

алгоритм
Помогите пожалуйста, Нужно решить задачу об узких местах.
В графе G(V,E) найти такой путь между вершинами s и t, в котором длина кратчайшей дуги максимальна.
  #2  
Старый 21.05.2010, 17:14
гость

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

Проще всего двоичный поиск + поиск в ширину.

Чуть быстрее, но больше кода - заменить длины ребер на отрицательные к ним, найти минимальное остовное дерево, и путь в дереве.
 


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

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