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 cost $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 timp: $O(N^5)$. (supraestimata)

Complexitate spatiu: $O(N^2)$.
h1(#Politie). 'I. Politie':problema/politie