Aceasta problema se rezolva in mod asemanator cu problema determinarii 'fluxului maxim':problema/maxflow, cu cateva modificari. Este din nou necesara constuirea _grafului rezidual_, care contine toate arcele din graful initial si, in plus, toate {_arcele de intoarcere_}. Astfel, pentru fiecare arc {$x->y$} de cost $z$ din graful initial se adauga in graful rezidual arcul y->x cu capacitatea $0$ si costul {$-z$}. Algoritmul ruleaza atat timp cat se mai poate introduce flux in retea. La fiecare pas, este necesara gasirea unui _drum de ameliorare_ de cost minim de la sursa la destinatie. Apoi, fluxul va fi incrementat pe acest drum cu valoarea maxima posibila (minimul diferentelor dintre capacitate si flux pentru fiecare arc de pe drum). Pentru a gasi drumul de ameliorare optim din punct de vedere al costului putem folosi un algoritm de drum minim care sa permita existenta costurilor negative pe arce (costurile arcelor de intoarcere), precum "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford. Algoritmul Bellman-Ford are complexitate $O(N*M)$, ceea ce conduce la o complexitate teoretica $O(N^2^*M^2^)$, insa in practica se comporta mai bine. Aceasta solutie obtine $50$ de puncte. O sursa pe 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. O sursa demonstrativa poate fi gasita 'aici':job_detail/238402?action=view-source.

Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de cost minim putem folosi si 'algoritmul lui Dijkstra':problema/dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim $Dist{~i~}$ ca fiind distanta minima de la $S$ la nodul $i$. Initial, folosind algoritmul lui Bellman-Ford, calculam valorile vectorului $Dist$. Apoi, fiecarui arc {$x->y$} de cost $z$ i se va asocia costul $z + Dist{~x~} - Dist{~y~}$. Costul arcelor devine pozitiv, altfel ar insemna ca $Dist{~x~} + z < Dist{~y~}$, ceea ce ar contrazice minimalitatea lui $Dist{~y~}$. Costul drumurilor minime difera fata de cele initale printr-o constanta, deci transformarea modifica doar costul acestora si nu le schimba cu alte drumuri. In consecinta, la fiecare pas vom putea folosi algorimul lui Dijkstra pentru a determina drumul de ameliorare si vom putea folosi distantele calculate cu acest algoritm pentru a modifica din nou costurile arcelor. Algoritmul lui Dijkstra are complexitate $O(M*logN)$, deci complexitatea totala devine $O(N*M^2^*logN)$, dar este iarasi supraestimata. Aceasta rezolvare obtine $100$ de puncte, iar o sursa demonstrativa se gaseste 'aici':job_detail/238424?action=view-source.

Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de cost minim putem folosi si 'algoritmul lui Dijkstra':problema/dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim $Dist{~i~}$ ca fiind distanta minima de la $S$ la nodul $i$. Initial, folosind algoritmul lui Bellman-Ford, calculam valorile vectorului $Dist$. Apoi, fiecarui arc {$x->y$} de cost $z$ i se va asocia costul $z + Dist{~x~} - Dist{~y~}$. Costul arcelor devine pozitiv, altfel ar insemna ca $Dist{~x~} + z < Dist{~y~}$, ceea ce ar contrazice minimalitatea lui $Dist{~y~}$. Costul drumurilor minime difera fata de cele initale printr-o constanta, deci transformarea modifica doar costul acestora si nu le schimba cu alte drumuri. In consecinta, la fiecare pas vom putea folosi algorimul lui Dijkstra pentru a determina drumul de ameliorare si vom putea folosi distantele calculate cu acest algoritm pentru a modifica din nou costurile arcelor. Algoritmul lui Dijkstra are complexitate $O(M*logN)$, deci complexitatea totala devine $O(N*M^2^*logN)$, dar este iarasi supraestimata. Aceasta rezolvare obtine $100$ de puncte, iar o sursa demonstrativa se gaseste 'aici':job_detail/245450?action=view-source.

h2. Aplicatii

* 'Renovare':problema/renovare
* 'Smen':problema/smen
* 'Adapost':problema/adapost

* 'Atac2':problema/atac2

== include(page="template/taskfooter" task_id="fmcm") ==
 

== include(page="template/taskfooter" task_id="fmcm") ==