printРабочее место участника

printЗадачи

2459. Золотая шахта

Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Питер, используя современные технологии, обнаружил местонахождение нескольких золотых самородков. Чтобы до них добраться, нужно выкопать тоннели либо от входа в шахту, либо от местонахождения какого-то другого самородка. На копание тоннеля необходимо затратить некоторую сумму, которая окупается после продажи найденных самородков.
Напишите программу, которая определит максимальную прибыль Питера и минимальную сумму, которая потребуется на первоначальных этапах для добычи тех самородков, которые обеспечат эту максимальную прибыль.
Первая строка ввода содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 100`) – количество самородков. Далее следует `n` строк, каждая строка содержит три целых числа – номер самородка `p_i`, от которого нужно копать тоннель до `i`-го самородка (`0\ ≤\ p_i\ <\ i`, 0 – вход в шахту), ценность `i`-го самородка `c_i` (`1\ ≤\ c_i\ ≤\ 100`) и стоимость прокладки тоннеля `d_i` (`1\ ≤\ d_i\ ≤\ 100`).
В первой строке вывести два целых числа – максимальная прибыль Питера и минимальная сумма, которая потребуется на первоначальных этапах для получения максимальной прибыли. Если прибыль не нулевая, то во второй строке вывести количество выкопанных самородков, а в третьей строке – порядок выкапывания самородков, обеспечивающий минимум средств, привлекаемых со стороны. Если существует несколько вариантов решения, выведите любой из этих вариантов.

Пример ввода 1

6
0 1 3
1 5 4
1 15 10
0 15 20
4 30 20
5 5 10

Пример вывода 1

9 21
5
4 1 2 3 5

Пример ввода 2

1
0 10 20

Пример вывода 2

0 0
loading