Fişierul intrare/ieşire:salvare.in, salvare.outSursăCampion 2002-2003
AutorMihai StroeAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insalvare.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content