APDM

apdm

==Include(page="template/taskheader" task_id="apdm")==

== include(page="template/taskheader" task_id="apdm") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| apdm.in | apdm.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="apdm") ==

==Include(page="template/raw")==
 
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]}.
 
h2. Cerinta
 
Sa se determine arborele partial de diametru minim al grafului dat!
 
h2. 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.
 
h2. Date de Iesire
Pe prima linie a fisierului apdm.out se va afisa diametrul arborelui obtinut.
 
h2. Restrictii
 
3<=N<=150;
 
N<=M<=5000
 
h2. 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 | | |
 
 
 
==Include(page="template/taskfooter" task_id="apdm")==