Ramane doar de sortat perechile si de testat pentru fiecare in parte daca este, de fapt, solutie a problemei. Nu toate perechile vor fi solutii, deoarece exista cateva cazuri marginale precum cel in care $2 * N$ este patrat perfect.

Complexitate timp: $O(sqrt(N) + sqrt(N)log(sqrt(N)))$.
Complexitate spatiu: $O(sqrt(N))$.
 
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]$ 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 spatiu: $O(N^2)$.

*Complexitate timp: $O(sqrt(N) + sqrt(N)log(sqrt(N)))$.*
*Complexitate spatiu: $O(sqrt(N))$.*

h1(#Politie). 'I. Politie':problema/politie

Alternativ, mai simplu, putem pur si simplu sorta muchiile crescator dupa categorie, si in caz de egalitate crescator dupa periculozitate si, la sfarsit, sa aplicam Kruskal. Practic simulam procedeul de deasupra.

Complexitate timp: $O(MlogM + Mlog*N)$.
Complexitate spatiu: $O(N + M)$.

*Complexitate timp: $O(MlogM + Mlog*N)$.*
*Complexitate spatiu: $O(N + M)$.*