Fişierul intrare/ieşire:berarii.in, berarii.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test5 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Berarii

Oamenii beau foarte multa bere in Romania. Pentru fiecare oras i din cele N orase ale tarii (numerotate de la 1 la N) se cunoaste cantitatea de bere Bi ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze K berarii in K orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste 2 orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras i si o berarie amplasata intr-un oras X, care este cea mai apropiata berarie de i. Costul transportului berii din orasul X in orasul i este dist(i,X)*Bi, unde dist(i,X) este distanta dintre orasul i si orasul X. Compania producatoare de bere doreste sa aleaga amplasarea celor K berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.

Date de intrare

Prima linie a fisierului de intrare berarii.in contine numarul intreg T, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine 2 numere intregi: N si K. Urmatoarele N linii contin cantitatile de bere cerute in fiecare oras: a i-a din aceste linii contine valoarea Bi. Urmatoarele N-1 linii contin cate 3 numere intregi: A, B si L, avand semnificatia ca exista o strada de lungime L intre orasele A si B.

Date de iesire

Pentru fiecare din cele T teste, in ordinea data in fisierul de intrare, veti afisa in fisierul de iesire berarii.out cate o linie continand valoarea minima posibila pentru costul maxim al transportului berii, in cazul unei amplasari optime a berariilor.

Restrictii

  • 1 ≤ T ≤ 21
  • 1 ≤ N ≤ 100 000
  • 1 ≤ K ≤ N
  • 1 ≤ Bi ≤ 10 000
  • Lungimea oricarei strazi este un numar intreg din intervalul [1, 10 000].

Exemplu

berarii.inberarii.out
1
4 2
3
4
2
7
1 2 10
2 3 21
2 4 57
42

Explicatie

Arborele este prezentat in figura de mai jos. Orasele in care vor fi construite berarii sunt colorate cu galben. Costul maxim al transportului berii, egal cu 42, se obtine intre orasul 3 si beraria amplasata in orasul 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content