Problema graf – OJI 2006, Clasa a 11-a

Enunțul problemei graf, de clasa a 11-a, dată în 2006 la OJI, se găsește pe InfoArena și PbInfo.

Rezumat

Se dă un graf neorientat conex, cu vârfurile etichetate de la $1$ la $n$, precum și două vârfuri distincte, notate cu $x$ și $y$. Trebuie să determinăm vârfurile care aparțin tuturor lanțurile optime (de lungime minimă) dintre $x$ și $y$.

Soluție

Notăm cu $lg(a, b)$ lungimea unui lanț optim între nodurile $a$ și $b$. Observăm că un nod $c$ aparține cel puțin unui lanț optim dintre $a$ și $b$ dacă și numai dacă $lg(a, b) = lg(a, c) + lg(c, a)$. De asemenea, dacă nu mai există alte noduri $d$, cu $lg(a, c) = lg(a, d)$, înseamnă că toate lanțurile optime de la $a$ la $b$ trec prin $c$.

Așadar, pentru a rezolva problema noastră, trebuie să căutăm toate nodurile ce îndeplinesc cele două condiții. Vom avea nevoie de niște parcurgeri în lățime pentru a calcula distanțele minime dintre noduri. O idee isteață este să facem doar două BFS-uri: Unul din $x$ și altul din $y$. Asta pentru că orice lanț de a cărui lungime avem nevoie are măcar o extremitate în $x$ sau în $y$. Ca să recapitulez:

1. Facem BFS din $x$ și din $y$, reținând rezultatele în vectorii $\mathrm{dpX}$ și $\mathrm{dpY}$.
2. Pentru fiecare nod $i$, dacă $\mathrm{dpX}[i] + \mathrm{dpY}[i] = \mathrm{dpX}[y]$, incrementăm $\mathrm{frq}[\mathrm{dpX}[i]]$ (numărul nodurilor ce se află pe un lanț elementar și cu distanța minimă până la $x$ egală cu $\mathrm{dpX}[i]$).
3. Parcurgem din nou nodurile pentru a vedea care are $\mathrm{frq}[\mathrm{dpX}[i]] = 1$. Acestea sunt nodurile ce aparțin tuturor lanțurilor optime dintre $x$ și $y$. Le adăugăm la vectorul $sol$.
4. Afișăm nodurile găsite la pasul anterior, precedate de numărul lor.

Sursă C++

Dacă ai vreo nedumerire cu privire la problema graf, lasă un comentariu și te voi ajuta 🙂