Această problemă este o aplicaţie la 'fluxul maxim de cost minim':http://infoarena.ro/problema/fmcm, graful trebuind să suporte anumite modificări înainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa si destinaţia fluxului) $S$ şi $D$. Vom trage muchii de la $S$ la fiecare nod din $L$ de cost $0$ şi capacitate $1$, precum şi de la fiecare nod din $R$ către $D$, tot de cost $0$ si capacitate $1$. Soluţia problemei va fi reprezentată de 'fluxul maxim de cost minim':http://infoarena.ro/problema/fmcm din această reţea. Datorită existenţei muchiilor de cost negativ, trebuie aplicat algoritmul Bellman-Ford, soluţia având astfel complexitate $O(FLUX*N*M)$. O astfel de abordare obţine 50 de puncte. O sursă pe această idee se poate găsi 'aici':http://infoarena.ro/job_detail/371522. Pentru punctaj maxim, trebuie folosită o coadă la implementarea Bellman-Ford-ului. Această implementare se poate găsi 'aici':http://infoarena.ro/job_detail/371534. De observat că deşi teoretic aceşti algorimti necesită un timp mare de execuţie, în practica se comportă mult mai bine.

În cazul problemelor când cuplajul maxim va fi $min(L,R)$, se recomandă folosirea 'Algoritmului lui Kuhn(Ungar)':http://infoarena.ro/algoritm-kuhn. Această abordare are complexitate $O(N^4^)$, însă ca şi fluxul normal, se comportă mult mai bine în practică.

În cazul problemelor când cuplajul maxim va fi $min(L,R)$, se recomandă folosirea Algoritmului lui Kuhn(Ungar). Puteţi citi despre acest algoritm 'aici':http://infoarena.ro/algoritm-kuhn şi 'aici':http://en.wikipedia.org/wiki/Hungarian_algorithm. Această abordare are complexitate $O(N^4^)$, însă ca şi fluxul normal, se comportă mult mai bine în practică.

h2. Aplicaţii