В Румъния
има N града,
свързани с M безплатни
пътища. Един
безплатен
път свързва точно
два града (например
Букурещ–Гюргево
или Букурещ–Констанца).
Всички
безплатни
пътища са
двупосочни и
от всеки град
може да се
отиде до
всеки друг с
използване
на
съществуващите
пътища. В резултат
на влизането
в
Европейския
съюз, държавата
трябва да
вземе мерки
за покриване
на европейските
правила за
пътната
инфраструктура.
Според тези
правила, поне
един от двата
града,
свързани с
безплатен
път, трябва
да има ранг
на
европейска
столица. Отначало
никой от N-те
града няма
ранг на
европейска
столица и за всеки
град е
известна
сумата (в
милиони Евро),
която е
необходима,
за да бъде
модернизиран
и да получи
съответния
ранг.
Тъй като
държавните
фондове са
ограничени,
определете
минималната
обща сума,
която трябва
да бъде изхарчена
за
издигането
на някои
градове в
ранг на
европейски
столици, така
че да бъдат
удовлетворени
изискванията
на Европейския
съюз.
За
решаването
на проблема правителството
е
предоставило
допълнителна
информация: във
всяка група
от 14
града има
двойка
градове A и B, за
които съществува
трети град C (не
непременно
от тази
група) така,
че ако бъдат
затворени
пътищата,
излизащи от C, няма
да е възможно
пътуването
от град A до град B само
по безплатни
пътища. Това
условие може
да се формулира
по следния
начин: Ако
разгледаме
пътната
инфраструктура
на Румъния
като неориентиран
свързан граф
с N върха
и M ребра,
всяка двусвързана
компонента на
този граф
съдържа ней-много
13 върха.
Вход
Входният файл ro.in съдържа на първия ред числата N и M, разделени с интервал, представляващи броя на градовете и броя на безплатните пътища. Следващият ред съдържа N цели числа Si (i от 1 до N) , разделени с интервал, представляващи сумата, която е необходима за обявяването на град i (i от 1 до N) в ранг на европейска столица. Всеки от следващите M реда, съдържа по две различни цели числа, разделени с интервал U и V, със значение, че има безплатен път от град U до град V.
Изход
Изходния файл ro.out трябва да съдържа на първия ред минималната сума, която държавата трябва да плати за удовлетворяване на европейските изисквания. На втория ред трябва да бъде изведен броя O на градовете, които ще бъдат повишени в ранг на европейски столици. Третият ред трябва да съдържа O на брой различни номера на градове, избрани за повишаване.
Ограничения
и пояснения
Пример
ro.in |
ro.out |
15 21 |
129 |
Ограничение
за време: 1.3
секунди на
тест
Ограничение
за памет: 30 Mb, от
които 1 Mb за
стек.
assistant Mugurel Ionut Andreica
Bucharest Polytechnic University, Automatics and Computers Department
mugurel_ionut@yahoo.com
Превод
на български:
Стоян Капралов