Козак Вус і найкраща країна
Козак Вус нарешті знайшов країну своєї мрії. Вона складається з міст, між якими не проходить жодна дорога. Звичайно, Вус захотів виправити цю ситуацію, і тому придумав різних двосторонніх доріг, які можна було би прокласти. За його задумом кожна дорога з'єднує два різні міста. Але виникла проблема: кожне місто може виділити на побудову доріг копійок, а для кожної дороги на її побудову пішло б копійок. Тому Козак вирішив, що йому вистачить побудувати декілька доріг так, аби всі міста стали сусідами. Міста називаються сусідами, якщо можливо дорогами країни дістатися з одного міста в інше.
При плануванні своїх робіт Козак Вус зрозумів одну річ: коли він будуватиме чергову дорогу, міста будуть об'єднуватися в групи сусідів. Щоб побудувати -ту дорогу, потрібно, щоб міста (або їх сусіди), між якими будується дорога, сумарно мали принаймні копійок (адже спершу потрібно заплатити за дорогу й лише потім будувати). Після побудови дороги бюджети міст об'єднуються, а вартість дороги вираховується з нової спільної казни.
Для кожного з міст ви знаєте число — кількість копійок, які може витратити місто . Для кожної з доріг ви знаєте числа , та , які означають, що дорога з'єднує міста та , а на її побудову потрібно копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати.
Вхідні дані
Перший рядок містить три цілі числа , та (, , ) — кількість міст, кількість доріг та номер блока відповідно.
Наступний рядок містить цілих чисел () — початкова кількість копійок в -му місті.
Кожний із наступних рядків містить по три цілі числа , та (, ) — номер міст, між якими -та дорога, та ціна її побудови відповідно.
Протокол взаємодії
Для того, щоб показати дороги, які потрібно побудувати, використовуйте таку функцію:
void add(integer i)
Ця функція будує дорогу під номером ().
Вам потрібно реалізувати одну функцію:
boolean solve(integer n, integer m, integer g, array of integers c, array of integers v, array of integers u, array of integers w)
— кількість міст у країні;
— кількість доріг, які можна прокласти;
— номер блока;
() — початкова кількість копійок у -тому місті;
та () — номери вершин, що з'єднує -та дорога;
() "— кількість копійок, необхідних на побудування -тої дороги;
ця функція повинна повертати
true
, якщо можливо правильно вибрати послідовність доріг, іfalse
, якщо ні.
Якщо ваша функція повертає true
, то до того, як вона його поверне, вона має зробити виклики функції add
для всіх побудованих доріг у тому порядку, у якому вони побудуються.
Вихідні дані
Якщо функція повертає false
, то в першому рядку буде виведено одне число .
Інакше в першому рядку буде виведено число — кількість побудованих доріг. У наступних рядках буде виведено по одному число — номер побудованої дороги.
Приклади
4 5 0 2 5 2 4 1 2 7 3 4 4 1 4 5 4 2 3 3 2 4
3 4 2 3
3 3 0 6 2 5 2 3 9 2 1 5 1 3 10
-1
Примітка
У першому прикладі країна складається з -ох міст, а план Козака Вуса складається з -и доріг. Спочатку будується дорога під номером : міста та об'єднаються у групу, а з їхнього загального бюджету сплачується копійки. На рахунку цієї групи залишається копійок. Після побудови дороги під номером бюджет групи буде складати копійки, адже приєдналося місто з бюджетом у копійки, а також витратили копійки на побудову дороги. Після побудови -ої дороги всі міста стануть сусідами, а їх загального бюджету вистачить, щоб заплатити копійок за дорогу.
У другому прикладі неможливо вибрати дороги та порядок їх побудови так, щоб усі міста стали сусідами й щоб за усі дороги було заплачено.
Оцінювання
( балів) ; ; ; ; якщо побудувати всі доріг, усі міста стануть сусідами;
( балів) ;
( балів) ; ;
( балів) ; усі однакові;
( балів) ;
( балів) ;
( балів) ;
( балів) без додаткових обмежень.