În
2005, România a fost sub ape. Sute de poduri s-au darmat, sute de drumuri
au fost distruse.
Primul ministru a înfiintat un consiliu pentru situatii de urgenta care
analizeaza harta tarii. Pe harta sunt marcate N
localitati importante. Localitatile sunt numerotate de la 1
la N. De asemenea, pe harta sunt
marcate drumurile existente între localitati pe care se poate circula,
precum si drumurile care au fost distruse. Pentru fiecare drum distrus este
specificat si costul estimat pentru reconstructia drumului.
Primul ministru doreste construirea unui numar minim de drumuri, astfel încât
în final sa existe legatura între oricare dintre cele N
localitati marcate pe harta. Daca exista mai multe solutii cu numar minim de
drumuri, va fi preferata aceea pentru care suma costurilor pentru reconstructie
este minima.
Cerinta
Determinati drumurile care
trebuie reconstruite, precum si suma minima cheltuita pentru reconstructie.
Date de intrare
Fisierul de intrare flood.in
contine pe prima linie un numar natural N,
reprezentând numarul de localitati.
Pe cea de a doua linie este scris un numar natural M,
care reprezinta numarul de drumuri existente pe care se poate circula.
Pe fiecare dintre urmatoarele M
linii sunt scrise câte doua numere naturale X
si Y, cuprinse între 1
si N, separate printr-un spatiu,
cu semnificatia "între localitatile X
si Y exista un drum pe care se
poate circula".
Pe urmatoarea linie este scris un numar natural P,
care reprezinta numarul de drumuri distruse.
Pe fiecare dintre urmatoarele P
linii sunt scrise câte trei numere naturale separate prin câte un
spatiu X, Y
si C, cu semnificatia "reconstructia
drumului dintre X si Y
costa C RON".
Date de iesire
Fisierul de iesire flood.out
va contine pe prima linie un numar natural nr,
reprezentând numarul minim de drumuri care trebuie reconstruite. Pe cea
de a doua linie va fi scris un numar natural S
care reprezinta suma costurilor pentru reconstructia celor nr
drumuri (minima posibil). Pe fiecare dintre urmatoarele nr
linii vor fi scrise câte trei numere naturale separate prin câte
un spatiu X Y C, cu semnificatia
"drumul dintre X si Y
de cost C va fi reconstruit".
Restrictii si precizari
0
< N <= 10 000
0 <= M, P <= 200
000
Costurile de reconstructie
sunt numere naturale nenule <=
1000
Drumurile dintre localitati
sunt bidirectionale.
Între doua localitati
pot exista mai multe drumuri de legatura.
Costurile totale de reconstructie
nu depasesc 2 000 000 000.
Înainte de inundatii
între oricare doua localitati exista legatura.
Se acorda punctaje partiale
astfel:
- pentru determinarea corecta a numarului minim de drumuri se acorda 20% din
punctajul pe test;
- pentru determinarea corecta a numarului minim de drumuri si a costului minim
se acorda 50% din punctajul pe test.