infoarena informatica de performanta

Ktree

• Prima solutie - Complexitate O(N⁵)

Se calculeaza o dinamica D[ i ][ j ][ k ] = costul minim daca in subarborele i tai k muchii si ai j noduri inaccesibile din nodul 1.

Pentru a calcula matricea D pentru un nod T, presupui ca ai calculate valorile lui D pentru toti fii lui T.
Apoi se mai construieste o dinamica A[ i ][ j ][ k ] = solutia daca consideri numai primii i fii ai lui T.

Solutia finala se afla in D[ 1 ][ N-K ][ M ].

• A doua solutie - Complexitate O(N⁴)

Aceasta solutie se bazeaza pe parcurgerea Euler a arborelui dat.

La inceput se calculeaza o dinamica A[ i ][ j ] = costul minim pentru ca in subarborele i sa se taie j muchii.

Apoi se mai calculeaza o dinamica D[ i ][ j ][ k ] = costul minim pentru a ajunge in pozitia i a parcurgerii Euler a arborelui, cu j noduri inaccesibile din nodul 1 si k muchii taiate.
Daca suntem pe pozitia i in parcurgere(fie T nodul de pe acea pozitie), avem 2 optiuni: nu taiem nodul: din D[ i ][ j ][ k ] -> D[ i+1 ][ j ][ k ], sau daca nodul T apare pentru prima data in parcurgere putem sa il taiem: D[ i ][ j ][ k ] -> D[pozitia finala a lui T in parcurgere + 1][j + nr de noduri din subarborele T][k + nrs], unde nrs ia valori de la 1 la M.

Solutia finala se afla D[ 2 * N ][ N-K ][ M ], deoarece parcurgere Euler a arborelui are 2 * N - 1 elemente.