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

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

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

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

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

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

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

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

Пример:

clinic.inclinic.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.

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



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