Diferențe pentru problema/flota între reviziile #4 si #13

flota

Flota

== include(page="template/taskheader" task_id="flota") ==

Mândria complexului de agrement de la Șmenu sunt plimbările cu vaporul pe salba de _N_ lacuri legate prin _M_ canale. Între oricare două lacuri există cel mult un canal cu lățimea întreagă și pozitivă. Un vapor de lățime _L_ poate naviga între două lacuri dacă există o cale între cele două lacuri formată numai din canale de lățime cel puțin egală cu _L_. Toate canalele sunt cu dublu sens.
 
Proprietarul complexului dorește să cumpere cât mai puține vapoare, toate identice, care să deservească toate lacurile. Deoarece prețurile variază pentru vapoare de diverse lățimi, proprietarul își notează _K_ lățimi și dorește să afle, în fiecare caz, de câte vapoare ar avea nevoie.

Mândria complexului de agrement de la Șmenu sunt plimbările cu vaporul pe salba de _N_ lacuri legate prin _M_ canale. Un vapor de lățime _L_ poate naviga între două lacuri dacă există o cale între cele două lacuri formată numai din canale de lățime cel puțin egală cu _L_. Proprietarul complexului, Trăiam Binescu, dorește să cumpere o flotă de vapoare, toate identice, care să deservească toate lacurile. Deoarece prețurile variază pentru vapoare de diverse lățimi, Binescu își notează _K_ lățimi și dorește să afle, în fiecare caz, numărul minim de vapoare necesare.

h2. Date de intrare

Următoarele _M_ linii conțin triplete de numere _x_ _y_ _w_, semnificând că între lacurile _x_ și _y_ există un canal de lățime _w_.

Ultimele _K_ linii conțin câte un număr _L [~i~]_, semnificând o posibilă lățime a vapoarelor cumpărate.

Ultimele _K_ linii conțin câte un număr _L [~i~]_, semnificând o posibilă lățime a vapoarelor de cumpărat.

h2. Date de ieșire

* 1 ≤ _N_ ≤ 50.000
* 1 ≤ _M_ ≤ 1.000.000
* 1 ≤ _K_ ≤ 100.000

* Toate lățimile canalelor și ale vapoarelor sunt întregi, pozitive, cel mult egale cu 1.000.000.000.

* Între oricare două lacuri există cel mult un canal. Toate canalele au dublu sens.
* Lățimile canalelor și ale vapoarelor sunt întregi, pozitive, cel mult egale cu 50.000.

h2. Exemplu

Este nevoie de 3 vapoare de lățime 20: unul pentru grupul de lacuri (2, 3, 5, 6) și câte unul pentru lacurile 1 și 4.
|

h3. Explicație
 
...
 

== include(page="template/taskfooter" task_id="flota") ==