| Fişierul intrare/ieşire: | flota.in, flota.out | Sursă | ad-hoc |
| Autor | Catalin Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 10240 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Flota
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.
Date de intrare
Fişierul de intrare flota.in conţine, pe prima linie, numerele N, M şi K.
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 de cumpărat.
Date de ieşire
În fişierul de ieşire flota.out se vor scrie K linii. Linia i va conţine un singur număr, respectiv numărul de vapoare care sunt necesare pentru lăţimea L i. Răspunsurile trebuie afişate în aceeaşi ordine cu întrebările.
Restricţii
- 1 ≤ N ≤ 50.000
- 1 ≤ M ≤ 1.000.000
- 1 ≤ K ≤ 100.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.
Exemplu
| flota.in | flota.out | Explicaţie |
|---|---|---|
| 6 9 5 1 2 5 1 6 10 2 3 40 2 6 20 3 4 5 3 5 35 3 6 80 4 5 15 5 6 60 20 90 3 60 30 | 3 6 1 4 3 | 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. Vapoarele de lăţime 90 nu pot naviga pe niciun canal, deci este nevoie de câte un vapor pentru fiecare lac. Vapoarele de lăţime 3 pot naviga pe toate canalele, deci este suficient unul singur. Este nevoie de 4 vapoare de lăţime 60: unul pentru grupul de lacuri (3, 5, 6) şi câte unul pentru lacurile 1, 2 şi 4. 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. |
