Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 14:03:49.
Revizia anterioară   Revizia următoare  

 

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

Vezi solutiile trimise | Statistici

APDM

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

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.outExplicatie
8 134In 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)
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?