Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 14:03:49.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | apdm.in, apdm.out | Sursă | Algoritmus |
| Autor | Cosmin Silvestru Negruseri | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
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.in | apdm.out | Explicatie |
| 8 13 | 4 | 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) |
| 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
