Bine v-am regasit,
Problema se rezolva in trei pasi, fiecare din ei executabili in O(N):
1) Aflarea, pentru fiecare muchie, a numarului de noduri situate la fiecare
capat al ei.
2) Calcularea sumei distantelor de la un nod oarecare (de pilda nodul 1) la
toate celelalte.
3) Aflarea nodului cu suma distantelor minima.
Iata un exemplu pentru arborele de mai jos:
+---+
| 2 |
+---+
/ \
/ \
/ \
+---+ +---+
| 5 | | 1 |
+---+ +---+
/ \
/ \
/ \
+---+ +---+
| 4 | | 3 |
+---+ +---+
1) In cazul muchiei 2-5, de exemplu, la capatul dinspre nodul 2 se afla doua
noduri (1 si 2), iar la capatul dinspre nodul 5 se afla trei noduri (3,
4 si 5). Etichetand in mod asemanator toate muchiile, se obtine arborele:
+---+
| 2 |
+---+
2/ \4
/ \
3/ \1
+---+ +---+
| 5 | | 1 |
+---+ +---+
4/ \4
/ \
1/ \1
+---+ +---+
| 4 | | 3 |
+---+ +---+
2) Se calculeaza suma distantelor din nodul 1 si se obtine 0+1+2+3+3=9.
3) Prin cautarea minimului se gaseste nodul 5 cu suma distantelor
0+1+1+1+2=5.
Iata in continuare solutia aleasa de Onor. Comisie pentru stocarea datelor
si pentru cei trei pasi.
** Stocarea datelor **
Pentru fiecare nod X se retine cate o lista de vecini. Pentru fiecare vecin
Y (al lui X) din aceasta lista se retine si numarul de noduri de la capatul
dinspre Y al muchiei (X,Y). De exemplu, pentru nodul 2, lista vecinilor va
contine undeva si nodul 5 impreuna cu numarul 3, deoarece la capatul dinspre
5 al muchiei 2-5 se afla 3 noduri. Pentru arborele de deasupra s-ar obtine
urmatorul vector de liste de vecini:
Nodul 1: (2,4)
Nodul 2: (1,1) -> (5,3)
Nodul 3: (5,4)
Nodul 4: (5,4)
Nodul 5: (2,2) -> (3,1) -> (4,1)
** Etichetarea muchiilor la ambele capete **
In metoda de stocare de mai sus, prima componenta a perechilor (vecinii
efectivi) se initializeaza la citirea datelor. Aflarea celei de-a doua
componente (numarul de noduri de la capatul unei muchii) presupune
tocmai etichetarea muchiilor. Aceasta se face recursiv, astfel:
Ne propunem sa etichetam muchia X-Y. Pentru capatul Y al muchiei,
procedam astfel:
a) Etichetam muchiile Y-Z1, Y-Z2, ..., Y-Zk unde Z1...Zk sunt nodurile
vecine lui Y (cu exceptia lui X).
b) In paralel, calculam Q=Q1+...+Qk, unde Qi este eticheta scrisa pe
capatul dinspre Zi al muchiei Y-Zi.
c) Etichetam capatele muchiei X-Y cu valoarile N-(Q+1) si respectiv Q+1.
** Calculul sumei distantelor dintr-un nod oarecare **
Pentru a afla S(X), suma distantelor de la nodul X la toate celelalte
noduri, facem o parcurgere in adancime pornind din nodul X si remarcam
ca:
--
S(X)= > Depth(i)
--
i=1..N
unde Depth(i) este nivelul in adancime, in cadrul parcurgerii, al
nodului i. Pentru poza de mai sus,
S(2)=Depth(1)+...+Depth(5)=1+0+2+2+1=6.
Dar adancimea unui nod se defineste recurent astfel:
Depth(i)=1+Depth(Tata(i)), Depth(radacina)=0.
** Calculul sumei distantelor pentru toate celelalte noduri **
Fie muchia X-Y in arbore. Ea este etichetata cu numerele Qx si Qy
respectiv inspre capetele X si Y. Sa presupunem ca am aflat suma
distantelor din nodul X, S(X). Cum aflam S(Y) in timp O(1) ?
Observam doua aspecte:
1) Cand "deplasam" originea (capitala) din X in Y, ne departam de Qx
noduri. Distanta pana la fiecare din aceste noduri creste cu o
unitate.
2) Pe de alta parte, de apropiem de Qy noduri, distanta pana la
fiecare din acestea scazand cu o unitate.
Asadar, S(Y)=S(X)+Qx-Qy. Sau, deoarece Qx+Qy=N:
S(Y)=S(X)+N-2*Qy
Cu aceasta relatie de recurenta, facem o parcurgere in adancime
pornind dintr-un nod oarecare (pentru care calculam suma distantelor
prin metoda ortodoxa de la punctul anterior) si calculam instantaneu
toate distantele.
Cam asta este, sper ca am fost clar si ca nu am gresit nimic esential.
Daca aveti intrebari, va rog sa le trimiteti pe lista publica
(problems) si le voi raspunde pronto (ma non troppo).
|
|
