Козак Вус і найкраща країна
Козак Вус і найкраща країна
Козак Вус нарешті знайшов країну своєї мрії. Вона складається з n міст, між якими не проходить жодна дорога. Звичайно, Вус захотів виправити цю ситуацію, і тому придумав m різних двосторонніх доріг, які можна було би прокласти. За його задумом кожна дорога з'єднує два різні міста. Але виникла проблема: кожне місто i може виділити на побудову доріг c_i копійок, а для кожної дороги j на її побудову пішло б w_j копійок. Тому Козак вирішив, що йому вистачить побудувати декілька доріг так, аби всі міста стали сусідами. Міста називаються сусідами, якщо можливо дорогами країни дістатися з одного міста в інше.
При плануванні своїх робіт Козак Вус зрозумів одну річ: коли він будуватиме чергову дорогу, міста будуть об'єднуватися в групи сусідів. Щоб побудувати j-ту дорогу, потрібно, щоб міста (або їх сусіди), між якими будується дорога, сумарно мали принаймні w_j копійок (адже спершу потрібно заплатити за дорогу й лише потім будувати). Після побудови дороги бюджети міст об'єднуються, а вартість дороги вираховується з нової спільної казни.
Для кожного з n міст ви знаєте число c_i — кількість копійок, які може витратити місто i. Для кожної з m доріг ви знаєте числа v_i, u_i та w_i, які означають, що дорога i з'єднує міста v_i та u_i, а на її побудову потрібно w_i копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати.
Вхідні дані
Перший рядок містить три цілі числа n, m та g (1 \leq n \leq 10^6, 0 \leq m \leq 10^6, 0 \leq g \leq 7) — кількість міст, кількість доріг та номер блока відповідно.
Наступний рядок містить n цілих чисел c_1, c_2, \ldots, c_n (1 \leq c_i \leq 10^6) — початкова кількість копійок в i-му місті.
Кожний із наступних m рядків містить по три цілі числа v_i, u_i та w_i (1 \leq v_i,u_i \leq n, 1 \leq w_i \leq 10^6) — номер міст, між якими i-та дорога, та ціна її побудови відповідно.
Протокол взаємодії
Для того, щоб показати дороги, які потрібно побудувати, використовуйте таку функцію:
void add(integer i)
Ця функція будує дорогу під номером i (1\leq i \leq m).
Вам потрібно реалізувати одну функцію:
boolean solve(integer n, integer m, integer g, array of integers c, array of integers v,
array of integers u, array of integers w)
n — кількість міст у країні;
m — кількість доріг, які можна прокласти;
g — номер блока;
c_i (|c|=n) — початкова кількість копійок у i-тому місті;
v_i та u_i (|v|=|u|=m) — номери вершин, що з'єднує i-та дорога;
w_i (|w|=m) "— кількість копійок, необхідних на побудування i-тої дороги;
ця функція повинна повертати
true
, якщо можливо правильно вибрати послідовність доріг, іfalse
, якщо ні.
Якщо ваша функція повертає true
, то до того, як вона його поверне, вона має зробити виклики функції add
для всіх побудованих доріг у тому порядку, у якому вони побудуються.
Вихідні дані
Якщо функція повертає false
, то в першому рядку буде виведено одне число -1.
Інакше в першому рядку буде виведено число q — кількість побудованих доріг. У наступних q рядках буде виведено по одному число x — номер побудованої дороги.
Приклад
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
Примітка
У першому прикладі країна складається з 4-ох міст, а план Козака Вуса складається з 5-и доріг. Спочатку будується дорога під номером 4: міста 2 та 4 об'єднаються у групу, а з їхнього загального бюджету сплачується 3 копійки. На рахунку цієї групи залишається 6 копійок. Після побудови дороги під номером 2 бюджет групи буде складати 4 копійки, адже приєдналося місто 3 з бюджетом у 2 копійки, а також витратили 4 копійки на побудову дороги. Після побудови 3-ої дороги всі міста стануть сусідами, а їх загального бюджету вистачить, щоб заплатити 5 копійок за дорогу.
У другому прикладі неможливо вибрати дороги та порядок їх побудови так, щоб усі міста стали сусідами й щоб за усі дороги було заплачено.
Оцінювання
(3 балів) n \leq 10; m = n - 1; c_i = 1; w_i = 1; якщо побудувати всі m доріг, усі міста стануть сусідами;
(8 балів) n,m \leq 10;
(12 балів) n,m \leq 10^5; c_i = 1;
(14 балів) n,m \leq 10^5; усі w_i однакові;
(16 балів) n,m \leq 10^3;
(19 балів) n,m \leq 10^5;
(12 балів) n,m \leq 5 \cdot 10^5;
(16 балів) без додаткових обмежень.