0287. Клинические проблемы

Имя входного файла:	clinic.in
Имя выходного файла:	clinic.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Ваш друг – главный врач маленькой, но очень престижной клиники. Его клиника состоит из n палат, соединённых n - 1 коридором. При этом клиника, естественно, представляет собой связное здание, то есть из любой палаты можно дойти до любой другой палаты, используя коридоры.

В начале i–го коридора стоит коробка, в которой лежит c_i пар одноразовых бахил. Каждый пациент, входя в коридор, надевает одну пару бахил и только потом идёт по коридору. Пройдя коридор, больной выкидывает бахилы. Если в коридоре не осталось бахил, то по этому коридору больше не пройдёт ни один больной. В каждой палате находится p_i больных, ожидающих осмотра. Главрач вызывает на осмотр сразу всех пациентов палаты разом, при этом пациенты начинают идти из своей палаты в направлении палаты номер 1 (в ней находится главврач). Если в каком-то коридоре на их пути закончились бахилы, то оставшиеся пациенты останутся в начале этого коридора и больше никуда не пойдут. К сожалению, за рабочий день главрач может осмотреть пациентов из не более чем k различных палат. Помогите ему выбрать осматриваемые палаты таким образом, чтобы он осмотрел как можно больше пациентов.

Формат входного файла

В первой строке входного файла дано два целых числа n и k – количество палат в клинике и максимальное число палат, которые может осмотреть доктор соответственно (1 ≤ k ≤ n ≤ 250). Во второй строке дано n целых чисел, p_i (0 ≤ p_i ≤ 10⁶)  – количество больных в i–ой палате. В следующих n - 1 строках дано описание коридоров в больнице. Описание коридора – три целых числа u, v, c (1 ≤ u < v ≤ n, 0 ≤ c ≤ 10⁶). Они означают, что в больнице есть коридор из палаты с номером v в палату с номером u, и в начале этого коридора стоит коробка, в которой лежит c пар бахил.

Формат выходного файла

В первую строку выходного файла выведите одно число – максимальное количество больных, которых может осмотреть главврач. В следующую строку выходного файла выведите число q – количество палат, которые главрач вызовет на осмотр. В следующую строку выведите q чисел – номера палат, которые главрач вызовет на осмотр. Если оптимальных решений несколько, то выведите любое.

Пример:

clinic.in	clinic.out
4 1 0 10 5 5 1 2 1 1 3 5 1 4 5	5 1 3
4 2 0 0 5 5 1 2 7 2 3 5 2 4 5	7 2 3 4
5 3 10 10 10 10 10 1 2 1 2 3 1 2 4 1 2 5 1	11 2 1 2

В первом примере доктору невыгодно вызывать больных из второй палаты, поскольку оттуда до доктора сможет дойти лишь один больной (остальные так и останутся у входа в коридор из второй палаты в первую). Во втором примере больные из палат 3 и 4 дойдут по коридорам до палаты 2, но в палату 1 сможет пройти только 7 больных из-за нехватки бахил. В третьем примере доктору нет смысла вызывать больных из ещё какой-либо палаты, поскольку им заведомо не хватит бахил для перехода из палаты 2 в палату 1 (однако вызов больных, которые заведомо не дойдут до доктора, ошибкой в этой задаче не считается).

Источник: Первенство ПетрГУ. Сентябрь 2012.

Обсудить       Отправить решение



Версия для печати