основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
Vollter
новичок


Рег.: 03/29/06
Сообщений: 18
Задача о максимальном пути в дереве
      #11961 - 08/28/06 10:45 AM

Не подскажете, что это за задача и как её решать? Спасибо.

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Artur
приобщившийся


Рег.: 11/19/04
Сообщений: 79
Из: Барнаул
Re: Задача о максимальном пути в дереве [Re: Vollter]
      #12052 - 09/08/06 05:53 AM

задача: найти в дереве две наиболее удаленные вершины. решается динамическим программированием.

--------------------
per aspera ad astra


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
it4_kp
опытный
*****

Рег.: 03/31/05
Сообщений: 221
Из: Архангельск
Re: Задача о максимальном пути в дереве [Re: Artur]
      #12053 - 09/08/06 11:26 AM

или просто двумя dfs

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: Задача о максимальном пути в дереве [Re: it4_kp]
      #12054 - 09/09/06 02:21 AM

Или одним...

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
necro
здесь был не раз


Рег.: 03/28/06
Сообщений: 28
Из: Украина. Киев
Re: Задача о максимальном пути в дереве [Re: _МГ_]
      #12080 - 09/14/06 04:26 AM

A pokonkretney ^)

--------------------
To be or not to be = true 8)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
megabot007
приобщившийся


Рег.: 12/05/05
Сообщений: 60
Из: Москва
Re: Задача о максимальном пути в дереве [Re: necro]
      #12081 - 09/14/06 05:10 AM

Задача решаетася для дерева одним dfs.
Берем произвольную вершину v. Пусть из нее можно пойти в вершины u1, u2, ..., uk, причем эти вершины "определяют" свои поддеревья U1, U2, ..., Uk. Либо 2 вершины лежат в одном из поддеревьев (проверяем все поддеревья), либо в 2-х разных поддеревьях. Тогда выберем 2 максимальных пути v -> Up, v -> Uq и сложим их.
Если же из текущей вершины можно пойти только в одну вершину u1, то еще надо проверить вариант (расстояние до максимально удаленной вершины от корня в поддереве U1) + 1 (v -> эта вершина).


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: Задача о максимальном пути в дереве [Re: megabot007]
      #12089 - 09/16/06 03:44 AM

Всё хорошо только для _каждой_ вершины нужно проверить на максимальность максимальный путь через предка данной вершины в DFS дереве. Для чего собственно и удобно писать второй DFS: для каждой вершины выбираем уже найденный максимальный путь среди потомков(без учета пути к прекам) и предка(через второй DFS) и передаём как параметр потомкам. Собственно это можно назвать и динамикой.
А можно и забить на всё что я написал, считать ответы для потомков, выбрав в качестве source вершины два разных листа дерева - так писать меньше.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 397 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 14586

Rate this topic

Переход в