Fişierul intrare/ieşire:mvc.in, mvc.outSursăAlgoritmiada 2013, Runda 1
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mvc

Vi se da un graf conex neorientat cu N noduri si N muchii, fiecare nod avand un cost. Vi se cere sa gasiti o submultime de noduri de cost minim astfel incat fiecare muchie din graf sa aiba incident cel putin un nod din submultime. Costul unei submultimi se defineste ca fiind suma costurilor fiecarui nod din submultime.

Date de intrare

Fişierul de intrare mvc.in va contine pe prima linie un singur numar intreg N, reprezentand atat numarul de noduri, cat si numarul de muchii. A doua linie va contine exact N valori, mai exact costurile nodurilor 1, 2 ... N.
Urmatoarele N linii vor contine fiecare cate 2 valori, x, y cu semnficatia ca exista muchie (neorientata) de la x la y.

Date de ieşire

În fişierul de ieşire mvc.out trebuie sa se afle un singur numar intreg reprezentand costul minim al unei submultimi astfel incat orice muchie sa fie incidenta la cel putin un nod din acea submultime.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 0 ≤ costul unui nod ≤ 10.000

Exemplu

mvc.inmvc.out
5
0 9 1 2 0
5 4
2 1
1 3
3 4
4 2
2

Explicaţie

Se aleg nodurile 1 si 4. Observam ca toate muchiile au exact un capat in submultimea {1, 4}. Observam ca si submultimea {1, 4, 5} este tot corecta, si are tot costul 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?