salvare

Salvare

== include(page="template/taskheader" task_id="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 în 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 întoarce la punctul de plecare. Timpul de rezolvare a unei urgente este dat de numarul de muchii parcurse de la punctul de salvare la nodul în 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 în timp minim (mai exact, maximul $M$ al timpilor de rezolvare sa fie minim).

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).

h2. Date de intrare

h3. Explicatie

Timpul maxim de rezolvare este 1. Se înfiinteaza doua puncte de salvare, în nodurile 1 si 4. Salvarea din 1 rezolva urgentele din 1 în timp 0 si urgentele din 2 si 3 în timp 1. Salvarea din 4 rezolva urgentele din 4 în timp 0 si urgentele din 5 în timp 1. Exista si alte solutii.

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.

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

1859