47
правок
Изменения
→Динамика по деревьям
=Динамика по деревьям=
Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять какоеЗанять корень каким-то ребро из корняребром* Не взять ни одного ребра из корнязанимать корень ребрами
В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.Если мы оставляем корень свободным, значит может разрешить всем его детям иметь в своих поддеревьях занятый корень. В ином случае мы можем разрешить не всем детям, а только тем, которые уже не заняты ребром из корня.
===Рекуррентная формула===
Теперь наши формулы имеют вид:<br>
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex><br>
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ aw[u,wx] \}\right\}</tex>
Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем кореньребра из корня if root==0: for u in child(v): sum1 += calculate(u, 1) #выполняем мемоизацию dp[v][root] = sum1 return sum1 sum2 max1 = adp[v][0] #случай 2: берем коренькакое-то ребро for u x in child(v): for t in childmax1 = max(u): # считаемmax1, что у нас нет ребер наверхcalculate(x, к корню sum2 0) += calculate(tv, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max(sum1, sum2)max1 return dp[v] child(v) -- возвращает детей вершины v[root]
==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.
