Pagina principala | Inscriere | Autentificare | Probleme | Clasament pe runde | Clasament | Anunturi | Echipa | Regulament | Linkuri


Vizualizare solutie

Titlul problemei: tree
Numarul problemei: 2
Runda: Runda 4 - concurs
Solutie: Pentru rezolvare se va folosi programare dinamica.

Se determina pentru fiecare nod NOD din arbore, numarul minim de arce care trebuie eliminate pentru a obtine un subarbore cu radacina NOD, care are i noduri (0 <= i <= P), retinandu-le in matricea NR pe linia NOD a nodului curent.

Rezultatul problemei este elementul minim de pe coloana P din matricea NR.

Constructia matricei NR se va face pornindu-se cu nodurile frunza, spre radacina arborelui.

La implementare se vor folosi doi vectori auxiliari: AUX si FINAL care vor retine urmatoarele:

In vectorul FINAL se vor depune rezultatele optime obtinute pe parcurs prin reuniunea subarborilor cu radacini in fiii lui NOD.

AUX va contine rezultatele optime pentru NOD luandu-se in considerare pe rand, rezultatele optime din FINAL.

Valorile din AUX se vor depune in matricea NR pe linia NOD.

Matricea ARB contine pe fiecare linie NOD (1<= NOD <= N) fii lui NOD.

Pasul 1:

Se coboara recursiv in arbore pana in frunze;

Pasul 2:

Daca NOD nu reprezinta frunza, se preiau rezultatele optime pentru primul fiu al nodului curent:

for i:=0 to p do aux[i]:=nr[arb[nod,1],i];

Pasul 3:

Se determina numarul minim de muchii care trebuie eliminate pentru a izola un subarbore cu radacina in NOD, ce are I descendenti (0...P-1).

Izolez optim un subarbore cu radacina in NOD avand i descendenti, ca minimul obtinut prin reuniunea unor subarbori cu radacini in fii lui NOD.

final[i] = min{aux[j]+nr[fiu,i-j]}

unde FIU parcurge toti ceilalti fii ai lui NOD, iar j<=i;

for k:=2 to vec[nod] do begin

fiu:=arb[nod,k];

for i:=0 to p do begin

min:=200;

for j:=0 to i do

if (aux[j]<>200) and (nr[fiu,i-j]<>200) then

if aux[j]+nr[fiu,i-j]<min then min:=aux[j]+nr[fiu,i-j];

final[i]:=min;

end;

for i:=0 to p do aux[i]:=final[i]; {reactualizez}

end;

nr[nod,0]:=1;

for i:=1 to p do nr[nod,i]:=aux[i-1];

Pasul 4:

Se va determina minimul pe coloana P in matricea NR.

Solutia se gaseste in arhiva de teste.

Pentru fiecare test de evaluare s-au acordat 10 puncte.

Inapoi

© 2002 - 2005 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com