Fişierul intrare/ieşire:apdm.in, apdm.outSursăAlgoritmus
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

APDM

Vom considera un graf conex, neorientat, cu N varfuri si M muchii. Fie D(i, j) distanta minima dintre varfurile i si j. Prin diametrul grafului vom defini valoarea Max { D(i,j) (1 ≤ i < j ≤ N) }.

Cerinta

Sa se determine arborele partial de diametru minim al grafului dat!

Date de Intrare

Pe prima linie a fisierului apdm.in se afla N si M. Pe fiecare din urmatoarele M linii se afla cate doua numere intregi sub forma x y, indicand prezenta unei muchii intre varfurile x si y.

Date de Iesire

Pe prima linie a fisierului apdm.out se va afisa diametrul arborelui obtinut.

Restrictii

  • 3 ≤ N ≤ 150
  • N ≤ M ≤ 5000

Exemplu

apdm.inapdm.out
8 13
1 2
1 5
2 4
1 7
2 3
3 4
3 8
4 5
4 6
5 6
5 7
6 7
6 8
4

Explicatie

In desen observam colorate cu verde muchiile unui arbore partial de diametru 4, acestea sunt: (1, 5), (2, 4), (3, 4), (4, 5), (4, 6), (5, 7), (6, 8)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content