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

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

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

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

а нах?
Сообщение от newbieman Посмотреть сообщение
Так я же ищу LCA для каждой пары вершин. А их много.
зачем это вам???
  #22  
Старый 06.04.2010, 22:33
Новичок

Отправить личное сообщение для newbieman Посмотреть профиль Найти все сообщения от newbieman
 
Регистрация: 02.04.2010
Сообщений: 18

Ну в смысле не совсем для каждой, но есть куча пар вершин, для которых нужно найти LCA, чтобы потом найти расстояние между ними.
  #23  
Старый 07.04.2010, 01:26
гость

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

Сообщение от newbieman Посмотреть сообщение
Ну в смысле не совсем для каждой, но есть куча пар вершин, для которых нужно найти LCA, чтобы потом найти расстояние между ними.
зачем вам искать LCA????? в том алгоритме что я рассказал вам НЕ НАДО явно вычислять LCA - этот алгоритм сам его ПОПУТНО же и вычисляет - та вершина на которой он остановится это и есть LCA. собственно это и есть один из простейших способов посчитать LCA. зачем вам еще какой-то алгоритм для LCA реализовывать???

LCA имеет смысл считать если у вас нет время просмотреть путь - т.е. сложность O(длина пути) слишком долго, а надо O(1) или O(log n). В вашей задаче - почситать все пути это НЕ НАДО.
  #24  
Старый 07.04.2010, 01:31
гость

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

Сообщение от гость Посмотреть сообщение
LCA имеет смысл считать если у вас нет время просмотреть путь - т.е. сложность O(длина пути) слишком долго, а надо O(1) или O(log n).
например, если надо быстро за O(1) найди ****ДЛИНУ ПУТИ***** а не сам путь - тогда пожалуйста, реализуйте фараха-колтона для быстрого LCA и будут вам длины путей за O(1)

Но вы же сказали что вам нужен сам путь. НЕЛЬЗЯ ПОЛУЧИТЬ АЛГОРИТМ СО СЛОЖНОСТЬЮ МЕНЬШЕ ЧЕМ Theta(k), ЕСЛИ АЛГОРИТМ УЖЕ ВЫВОДИТ ПОРЯДКА Theta(k) ДАННЫХ.

(конечно, это утверждение для стандартной, последовательной RAM-машины, а не каких-нибудь параллельных моделей вычисления)
  #25  
Старый 11.04.2010, 19:08
Новичок

Отправить личное сообщение для newbieman Посмотреть профиль Найти все сообщения от newbieman
 
Регистрация: 02.04.2010
Сообщений: 18

Всё, я понял и разобрался. Огромное вам спасибо. Извинияюсь, что сразу не въехал =)
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Задачи 0 18.03.2009 18:03
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Графы 0 18.03.2009 03:21
помогите написать программу поиск в глубину на графе гость Реализация, исходники, языки 2 17.01.2009 13:51
Обход графа в глубину гость Реализация, исходники, языки 2 20.11.2007 11:47