h2. Indicatii de rezolvare
Aceasta problema se rezolva in mod asemanator cu problema determinarii 'fluxului maxim':problema/maxflow, cu cateva modificari. Este din nou necesara constuirea _grafului rezidual_, in felul urmator: pentru fiecare arc din graful initial se mai adauga cate un arc (arc de intoarcere) orientat invers cu capacitatea $0$ si cu costul opus ({$-z$}). Algoritmul ruleaza atat timp cat se mai poate introduce flux in retea. La fiecare pas, este necesara gasirea unui drum de cost minim vaid (fluxul de pe fiecare arc sa fie strict mai mic decat capacitatea) de la sursa la destinatie numit _drum de augmentare_. Apoi, fluxul va fi incrementat pe acest drum cu valoarea maxima posibila (minimul din diferentele dintre capacitate si flux pentru fiecare muchie de pe drum). Pentru a gasi drumul de augmentare, o alternativa ar fi sa folosim algoritmul "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford, datorita prezentei costurilor negative pe arce. Chiar daca $z ≥ 0$, arcele de intoarcere ar fi tot negative, deci si cu aceasta restrictie drumul de augmentare ar trebui cautat tot cu algoritmul Bellman-Ford. Acest algoritm are complexitate $O(N*M)$, ceea ce conduce la o complexitate totala $O(N^2^*M^2^)$, insa in practica se comporta mai bine. Aceasta solutie obtine $50$ de puncte; o sursa ce implementeaza aceasta idee poate fi gasita 'aici':job_detail/238401?action=view-source. Algoritmul Bellman-Ford poate fi rafinat folosind o coada pentru a mentine nodurile ce mai pot contribui la imbunatatirea costurilor. Desi complexitatea ramane aceeasi, in practica, timpul de rulare scade simtitor. O astfel de abordare obtine $70$ de puncte si o sursa demonstrativa poate fi gasita 'aici':job_detail/238402?action=view-source.

Pentru a gasi drumul de augmentare, poate fi folosit si 'algoritmul lui Dijkstra':problema/dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim $Dist[i]$ distanta minima de la $S$ la nodul $i$. Initial, folosind algoritmul lui Bellman-Ford calculam $dist[i]$. Apoi costul fiecarui arc $z[x-y]$ va fi inlocuit cu $z[x->y] + Dist[x] - Dist[y]$. Costul arcelor devine pozitiv, altfel ar insemna ca $Dist[x] + z[x->y] < Dist[y]$, ceea ce ar contrazice minimalitatea lui $Dist[y]$. Costul drumurilor minime difera fata de cele initale prin constanta $Dist[x]-Dist[y]$, deci transformarea nu schimba drumul minim. Apoi, la fiecare pas vom putea folosi algorimul lui Dijkstra pentru a determina drumul de augmentare si vom putea folosi distantele calculate cu acest algoritm pentru a modifica din nou costurile arcelor. Algoritmul lui Dijkstra are complexitate $O(MlogN)$ si complexitatea totala este O(N*M^2^*logN), din nou supraestimata. Aceasta rezolvare obtine $100$ de puncte si o sursa ce foloseste aceasta idee se afla 'aici':.
h2. Aplicatii