Изменения
→Псевдокод
=== Псевдокод ===
<font color = darkgreen>// в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] </font color = darkgreen> '''function''' dfs(x: '''int''', a: '''int[]''', b: '''int[]''', c: '''int[]'''), w: <font color = darkgreen>//в основной процедуре вызываем dfs от корня(root)'''int[][]''', после этого ответ будет хранится в cCh: '''int[root] </font color = darkgreen>'''):
'''for''' (i : Ch[x])
dfs(i, a, b, c, w, Ch) a[x] = max(a[x], b[i] + w[x][i] - с[i]) <font color = darkgreen>// по формуле выше, но без b[x] (прибавим его один раз в конце) </font color = darkgreen>
b[x] += с[i]
a[x] += b[x] <font color = darkgreen>// так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x</font color = darkgreen>
c[x] = max(a[x], b[x])
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Другие задачидинамического программирования]][[Категория:Алгоритмы на графах]]
