Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | ct.in, ct.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
CT
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
CT
Intr-o tara exista N orase, numerotate cu numere de la 1 la N. Orasele sunt conectate de strazi astfel incat exista un singur mod de a ajunge de la un oras la altu folosind strazile existente. In aceasta tara K organizatii teroriste fac planuri pentru distrugerea lumii, de aceea echipa CT s-a decis sa ii opreasca. Fiecare grupare terorista are cate o baza in doua din orasele tarii(deasemenea poate avea ambele baze in acelasi oras). Zilnic teroristii merg de la o baza la alta folosind strazile existente, ducand cu ei planurile pentru dominarea lumii. Bombardarea unui oras C va distruge acel oras si toate perechile de orase pentru care drumul dintre ele trecea prin orasul C vor ramane deconectate. Neutralizarea unei grupari teroriste consta in deconectarea oraselor care contin bazele gruparii respective sau in bombardarea a cel putin un oras care contine o baza a gruparii respective. Deoarece bombardarea oraselor implica si moartea unor civili neajutorati echipa CT doreste sa bombardeze cat mai putine
orase pentru a neutraliza toate cele K organizatii teroriste.
Cerinta
Gasiti numarul minim de orase pe cae echipa CT trebuie sa le bombardeze.
Date de Intrare
Prima linie a fisierului de intrare ct.in contine T, numarul de teste din fisier apoi vor urma cele T teste. Pe prima linie a fiecarui test se afla doua numere N si K numarul de orase respectiv numarul gruparilor teroriste. Urmeaza apoi N-1 linii continand cate doua numere x, y cu semnificatia exista strada intre orasele x si y. In continuare vor fi K linii, pe linia i aflandu-se doua numere ce reprezinta orasele in care se afla sediul organizatiei i.
Date de Iesire
In fisierul ct.out vor exista T linii fiecare continand numarul minim de orase ce trebuie bombardate pentru tara respectiva.
Restrictii si precizari
. 1 <= N <= 100.000
. 1 <= K <= 100.000
. 1 <= T <= 5
Exemplu
ct.in | ct.out |
1 | 2 |
11 5 | |
1 2 | |
2 3 | |
3 4 | |
2 5 | |
5 6 | |
5 11 | |
7 1 | |
10 7 | |
8 7 | |
9 8 | |
4 6 | |
3 11 | |
5 9 | |
10 9 | |
8 2 |
Explicatii
Se pot bombarda orasele 2 si 7 neutralizand astfel toate gruparile teroriste.