| Fişierul intrare/ieşire: | salvare.in, salvare.out | Sursă | Campion 2002-2003 |
| Autor | Mihai Stroe | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Salvare
Se considera un arbore (graf neorientat, conex si aciclic) cu N varfuri. In nodurile acestui arbore locuiesc oameni, iar muchiile au lungime 1. Se doreste infiintarea in noduri ale arborelui a K puncte de salvare, astfel incat locuitorii arborelui sa fie ajutati cat mai rapid in caz de urgente.
La aparitia unei urgente intr-un anumit nod, o masina a Salvarii pleaca dintr-unul din cele mai apropiate puncte de salvare catre nodul respectiv, pentru a acorda primul ajutor, dupa care se intoarce la punctul de plecare. Timpul de rezolvare a unei urgente este dat de numarul de muchii parcurse de la punctul de salvare la nodul in care a aparut urgenta. Se considera ca pana la intoarcerea salvarii in punctul de plecare nu pot aparea urgente noi.
Sa se stabileasca nodurile in care se vor infiinta puncte de salvare, astfel incat orice urgenta sa fie rezolvabila in timp minim (mai exact, maximul M al timpilor de rezolvare sa fie minim).
Date de intrare
Prima linie a fisierului de intrare salvare.in contine numarul intreg N, reprezentand numarul de varfuri ale arborelui. A doua linie a fisierului contine numarul intreg K, reprezentand numarul de puncte de salvare. Urmatoarele N-1 linii contin cate doi intregi distincti a si b, separati printr-un spatiu, avand semnificatia ca exista muchie intre varful numerotat cu a si cel numerotat cu b.
Date de iesire
In fisierul salvare.out veti afisa:
- pe prima linie numarul M, maximul timpilor de rezolvare;
- pe a doua linie K numere distincte intre 1 si N, ordonate crescator, nodurile in care se vor infiinta puncte de salvare
Restrictii
- 1 ≤ N ≤ 1000
- 1 ≤ K ≤ 300
- Varfurile sunt numerotate cu numere distincte intre 1 si N
- Daca exista mai multe solutii, se va afisa una oarecare
Exemplu
| salvare.in | salvare.out |
|---|---|
| 5 2 4 1 1 3 1 2 4 5 | 1 1 4 |
Explicatie
Timpul maxim de rezolvare este 1. Se infiinteaza doua puncte de salvare, in nodurile 1 si 4. Salvarea din 1 rezolva urgentele din 1 in timp 0 si urgentele din 2 si 3 in timp 1. Salvarea din 4 rezolva urgentele din 4 in timp 0 si urgentele din 5 in timp 1. Exista si alte solutii.
