== include(page="template/taskheader" task_id="diametru") ==
Poveste şi cerinţă...
Stelica, student eminent la Liceul International al Structurilor de date se pregateste de Bacalaureat si, ca orice alt elev de varsta lui, atunci cand gaseste ceva interesant fara nicio legatura cu Bacalaureatul amana tot ce are de facut ca sa studieze ce a gasit.
Astazi el a descoperit algoritmul pentru determinarea diametrului unui graf (diametrul unui graf este definit ca maximul distantei minime intre $2$ noduri). Este un algoritm foarte simplu si usor de implementat asa ca evident l-a facut sa se gandeasca la tot felul de aplicatii. Algoritmul este urmatorul (descris in pseudocod):
==code(python) |
INTRARE: un graf neorientat conex G(V, E) cu nodurile etichetate de la 1 la |V| (cardinal de V)
nod_curent <- 1
raspuns <- 0
pentru K pasi executa
afla distanta de la nod_current la toate celelalte (de exemplu printr-un bfs http://infoarena.ro/problema/bfs )
next <- nodul cel mai indepartat de nod_curent astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa
in caz de egalitate se alege next la distanta maxima de nod_curent
in caz de egalitate si dupa criteriul de mai sus se alege next de valoare minima
raspuns <- max(raspuns, distanta dintre nod_curent si next)
nod_curent <- next
==
Acest algoritm, are o proprietate foarte interesanta: cand graful $G$ e arbore se poate alege $K = 2$ si sigur variabila $raspuns$ va contine la final diametrul arborelui. Pentru grafuri lucrurile nu stau chiar asa. Chiar si-asa Stelica este foarte concentrat pe acest algoritm si nu mai invata nimic pentru bacalaureat asa ca parintii lui v-au rugat sa gasiti un graf $G$ astfel incat sa fie nevoie de un $K$ cat mai mare pentru ca algoritmul sa determine raspunsul. Va vor puncta in functie de cat de mare veti reusi sa faceti $K$-ul pentru a-i arata lui Stelica ca nu este un algoritm bun si sa nu-si mai piarda timpul cu el.
Astfel daca veti reusi sa faceti $K$-ul sa fie cel putin:
* $10$ - veti primi 30 de puncte
* $450$ - veti primi 50 de puncte
* $10.000$ - veti primi 75 de puncte
* $60.000$ - veti primi 100 de puncte
h2. Date de intrare
Fişierul de intrare $diametru.in$ ...
Fişierul de intrare $diametru.in$ va contine textul integral al operei Floare Albastra de Mihai Eminescu pentru cei aflati in aceeasi situatie cu Stelica.
h2. Date de ieşire
În fişierul de ieşire $diametru.out$ ...
În fişierul de ieşire $diametru.out$ trebuie sa contina descrierea unui graf neorientat conex.
Pe primul rand se vor gasi $N$ si $M$, numarul de varfuri, respectiv numarul de muchii din graful generat de dumneavoastra.
Pe urmatoarele $M$ linii trebuie sa se gaseasca $2$ numere $x{~i~}$ si $y{~i~}$ cu semnificatia ca exista o muchie intre nodul cu indicele $x{~i~}$ si cel cu indice $y{~i~}$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ numarul de noduri din graful generat de dumneavoastra ≤ 500$
* Graful generat trebuie neaparat sa fie conex, altfel veti primi "Fisier de iesire corupt"
* Nu aveti voie sa aveti muchii de la un nod la el insusi sau multiple muchii intre acelasi perechi de noduri
h2. Exemplu
table(example). |_. diametru.in |_. diametru.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| Iar te-ai cufundat în stele
Si în nori si-n ceruri nalte?
De nu m-ai uita încalte,
Sufletul vietii mele.
...
| 4 5
1 2
1 3
1 4
2 3
2 4
|
h3. Explicaţie
...
Pentru acest output veti lua $0$ puncte dar este un exemplu de graf unde nu se gaseste diametrul cu K = 2, trebuie K >= 3.
Algoritmul va functiona asa:
* Din nodul $1$ se merge in nodul $2$ care e la distanta $1$ (toate sunt egal departate de $1$ dar $2$ are valoarea ea mai mica)
* Din nodul $2$ se merge in nodul $3$ care e la distanta $1$ (toate sunt egal departate de $2$ dar perechea $(1, 2)$ a fost deja aleasa iar dintre $3$ si $4$, $3$ are valoarea mai mica)
* Din nodul $3$ se merge in nodul $4$ care e la distanta $2$ (s-a ales $4$ fiindca e singurul la distanta $2$ de nodul $3$, restul fiind doar la distanta $1$)
== include(page="template/taskfooter" task_id="diametru") ==
