Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 15:10:19.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:asmin.in, asmin.outSursăONI 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Asmin

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

Se considera un arbore (graf conex aciclic) cu N varfuri, fara radacina fixata. Drept radacina, poate fi ales oricare dintre varfuri. Sa presupunem ca a fost ales varful cu numarul T. Intre oricare varf si T exista un drum unic care contine fiecare varf al arborelui cel mult o singura data (un drum intre varfurile i si j este o secventa de varfuri, care incepe cu i, se termina cu j, iar intre oricare doua varfuri consecutive exista o muchie in arbore). Fiecarui varf i(inclusiv T) trebuie sa i se asocieze o valoare V~i~, mai mare sau egala cu 0, astfel incat suma valorilor varfurilor de pe drumul dintre i si radacina T, impartita la K, sa dea restul R~i~. Se defineste costul arborelui cu radacina fixata in T, C~T~, ca fiind suma valorilor asociate fiecarui nod. Dintre toate posibilitatile de alegere a valorilor V~i~ care respecta conditia precizata anterior, se va alege aceea pentru care C~T~ este minim.
Se constata usor ca alegand alt varf drept radacina, de exemplu, varful S(diferit de T), C~S~ nu este neaparat egal cu C~T~.

Cerinta

Dandu-se un arbore cu N varfuri, un numar intreg K si valorile R[i], i=1,2,..,N, corespunzatoare fiecarui varf, determinati acele varfuri T care pot fi alese drept radacina, pentru care costul C[T] este minim (adica C[T]<=C[S], oricare ar fi S diferit de T), precum si costul respectiv.

Date de Intrare

Pe prima linie a fisierului de intrare asmin.in se afla 2 valori intregi: N si K. Pe urmatoarele N-1 linii se afla cate doua numere intregi a b, separate printr-un spatiu, avand semnificatia ca exista muchie intre varfurile a si b. Varfurile sunt numerotate de la 1 la N. Pe urmatoarea linie se afla N numere intregi, reprezentand valorile R[i], i=1,2,..,N.

Date de Iesire

Pe prima linie a fisierului de iesire asmin.out se vor afisa doua valori intregi: C si M. C reprezinta costul minim posibil al arborelui. M reprezinta numarul de varfuri care pot fi alese drept radacina si pentru care se obtine costul C. Pe a doua linie se afla M numere intregi separate prin cate un spatiu, scrise in ordine crescatoare, reprezentand numerele varfurilor ce pot fi alese ca radacina astfel incat sa se obtina costul C.

Restrictii si precizari

. 2 <= N <= 16.000

. 2 <= K <= 1.000

. 0 <= R[i] <= K-1

Exemplu

asmin.in asmin.out Explicatie
5 3 5 2 Valorile asociate varfurilor celor doi arbori sunt urmatoarele:

1 2 1 5 V1=0 V2=1 V3=2 V4=0 V5=2

1 3 V1=2 V2=1 V3=2 V4=0 V5=0

2 4

2 5

0 1 2 1 0

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?