h1(#Tribut). 'C. Tribut':problema/tribut

Vom aborda problema cu ajutorul tehnicii de "Flux maxim":http://www.infoarena.ro/problema/maxflow. Astfel, construim o retea in care fiecare sistem solar $i$ are asociat nodul $i$, iar fiecare uniune comerciala $j$ nodul $N + j$. Sursa si destinatia vor fi alese convenabil astfel incat sa nu se suprapuna cu nodurile necesare. Vom trage un arc de la sursa la fiecare sistem solar $i$ printr-o muchie de capacitate $solarSystemTribute[i]$, cat si un arc de la fiecare planeta la fiecare dintre uniunile comerciale din care face parte, cu capacitate $INFINIT$. In final, tragem arcuri de la uniunea comerciala $i$ la destinatie, de capacitate $unionTribute[i]$. Ramane sa rulam algoritmul de flux pe acest graf, iar fluxul maxim rezultant reprezinta solutia problemei.

Vom aborda problema cu ajutorul tehnicii de "Flux maxim":http://www.infoarena.ro/problema/maxflow. Astfel, construim o retea in care fiecare sistem solar $i$ are asociat nodul $i$, iar fiecare uniune comerciala $j$ nodul $N + j$. Sursa si destinatia vor fi alese convenabil astfel incat sa nu se suprapuna cu nodurile necesare. Vom trage un arc de la sursa la fiecare sistem solar $i$ printr-o muchie de capacitate $solarSystemTribute[i]$ si de la fiecare planeta la fiecare dintre unionile comerciale din care face parte, cu capacitate suficient de mare. In final, tragem arcuri de la uniunea comerciala $i$ la destinatie, de capacitate $unionTribute[i]$. Ramane sa rulam algoritmul de flux pe acest graf, iar fluxul maxim rezultant reprezinta solutia problemei.

Complexitate timp: $O(N^5)$ (supraestimata).
Complexitate spatiu: $O(N^2)$.