| 86
|

h3. Explicaţie

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.
 
h2. Aplicatii
 
Pentru a determina cuplajul de cost minim intr-un graf bipartit se foloseste acelasi algoritm ca cel prezentat in aceasta problema. De asemenea, pentru a determina cuplajul de cost maxim intr-un graf biparit, folosim acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz, rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei muchii si costul fluxului obtinut pe graful modificat. Algoritmul prezentat in aceasta problema este necesar pentru a rezolva mai multe probleme de informatica, cum ar fi:
 
* 'Cc':problema/cc
* 'Traseu':problema/traseu
* 'Renovare':problema/renovare
* 'Smen':problema/smen
* 'Adapost':problema/adapost

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