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 ameliorare_. 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 acest drum, o alternativa ar fi sa folosim algoritmul "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford, datorita prezentei costurilor negative pe arce. 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/237163?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 aproximativ $70$ de puncte si o sursa demonstrativa poate fi gasita 'aici':job_detail/237554?action=view-source.

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 ameliorare_. 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 ameliorare, o alternativa ar fi sa folosim algoritmul "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford, datorita prezentei costurilor negative pe arce. 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/237163?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 aproximativ $70$ de puncte si o sursa demonstrativa poate fi gasita 'aici':job_detail/237554?action=view-source.

h2. Aplicatii