h2. Indicatii de rezolvare

Aceasta problema se rezolva in mod asemanator cu problema determinarii 'fluxului maxim':problema/maxflow, cu cateva modificari. Pentru fiecare arc din graf se mai adauga cate un arc (arc de intoarcere) orientat invers cu capacitatea $0$ si cu costul opus celui initial ({$-z$}). Pe acest graf se pune problema gasirii unor drumuri de cost minim de la sursa la destinatie, care sa respecte conditiile unui graf rezidual. O prima idee ar fi folosirea algoritmului "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford, datorita costurilor negative ce apar pe arcele de intoarcere. Astfel complexitatea totala este $O(N^2^*M*B)$, unde $B$ este o limita superioara a capacitatii totale a unui nod. O 'solutie':job_detail/237163?action=view-source folosind o implementare naiva a algoritmului Bellman-Ford obtine $50$ de puncte. O data cu rafinarea implementarii algoritmului Bellman-Ford, folosind o coada pentru a mentine nodurile ce au potential pentru micsorarea distantei, viteza de rulare se imbunatateste simtitor. O 'astfel de implementare':job_detail/237164 obtine in jur de $70$ de puncte.

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.

h2. Aplicatii