Pagini recente » Diferente pentru problema/colorare intre reviziile 1 si 2 | Diferente pentru problema/melodii intre reviziile 15 si 9 | Atasamentele paginii Profil eusebiu_2002 | Diferente pentru utilizator/theboys intre reviziile 3 si 4 | Diferente pentru problema/berarii intre reviziile 2 si 8
Diferente intre titluri:
Diferente intre continut:
== include(page="template/taskheader" task_id="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 $B{~i~}$ 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 $X$. Costul transportului berii din orasul $X$ in orasul $i$ este $dist(i,X)*B{~i~}$, 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.
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 $B{~i~}$ 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)*B{~i~}$, 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.
h2. Date de intrare
h2. Date de iesire
Pentru fiecare din cele $T$ teste, in ordinea data in fisierul de intrare, afisati o linie continand valoarea minima posibila pentru costul maxim al transportului berii, in cazul unei amplasari optime a berariilor.
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.
h2. Restrictii
* $1 ≤ T ≤ 21$
* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ N$
* $1 ≤ B{~i~} ≤ 10 000$
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$.
!problema/berarii?berarii.jpg!
== include(page="template/taskfooter" task_id="berarii") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
