Тема: ДП
В чем суть динамики по дереву? Где и когда применима ?
1 2009-08-31 13:54:24 Отредактировано Zayakin_Andrey (2009-08-31 13:55:55)
2 2009-08-31 15:01:54 Отредактировано it4.kp (2009-08-31 15:02:38)
Re: ДП
Суть в том, что часто задача для вершины естественным образом сводится к задаче для связанных вершин, а так как в дереве нет циклов, то применима динамика. Динамику обычно запускают из одной вершины, тем самым представляя дерево подвешенным за эту вершину (корень). Тогда у каждой вершины, кроме корня, будет ровно один родитель и несколько детей.
3 2009-10-07 18:53:50 Отредактировано Baur (2009-10-07 18:56:58)
Re: ДП
Пример задачи на динамику по дереву (была на сайте acm.albertina.ru который в данный момент недоступен):
Дано взвешенное дерево с N вершинами (N = 100000) Найти сумму расстояний между всеми вершинами.
Решение:
Посчитаем, во скольких путях между вершинами участвует какое-либо ребро. Пусть left - количество вершин слева от ребра, а right - справа от ребра.
Тогда количество путей, проходящих через ребро - (left+1)*(right+1) // концы ребра тоже надо учитывать
И так для каждого ребра считаем эту величину и умножаем на вес ребра и прибавляем к общей сумме. Как это реализовать? В обычном DFS добавим переменную left - (что она означает, сказано выше). "Наверх" возвращаем left+1. Для вершин, где нет соседей (для листов) возвращаем 1("саму себя"). Соответственно, right = N - left и "вклад" ребра в сумму считается на лету: left*(N-left)*weight
P.S Если я не ошибаюсь, нахождение диаметра дерева - тоже на эту тему.
Re: ДП
Ну диаметр дерева можно находить и просто 2-мя бфсами.
Re: ДП
KADR пишет:
Ну диаметр дерева можно находить и просто 2-мя бфсами.
А как это сделать?
Re: ДП
из любой вершины пускаем BFS. по его результатам находим самую далекую вершину. Потом от этой самой далекой вершины снова запускаем БФС, и расстояние до новой самой дальней вершины будет диаметром дерева.
Джеймс Гослинг с нами!
Re: ДП
А как это доказать?
Re: ДП
Zayakin_Andrey пишет:
А как это доказать?
Напиши сюда свой mail, я туда доказательство отправлю, просто его легче несколькими рисунками показать и прокомментировать, чем писать скучный и длинный текст.