geek code Ответов: 0

Максимизируйте прибыль на ненаправленном дереве.

Я столкнулся с этой проблемой, давая образец теста. Проблема была в том, что мы дали дерево, которое не направлено. Мы можем начать с любого узла по нашему выбору. Изначально у нас есть мощность "Р", и при переходе от одного узла к другому мы теряем некоторую мощность "х" (рассматриваем как стоимость путешествия) и получаем некоторую прибыль "у". Итак, мы должны сказать, что какова максимальная прибыль, которую мы можем получить с данной силой ?

Example: First line contains number of nodes and initial power

Next n-1 lines contains node-node-cost-profit

5 4

1 2 1 2

1 3 2 3

1 4 2 4

4 5 2 2

Answer => 7. We can start from 4 and go to 1 and than to 3.


Что я уже пробовал:

Я применил DFS, проверив каждый отдельный путь, но есть ли способ решить эту проблему более оптимально.

0 Ответов