4 5 10 2 1 7
|

h3. Explicaţie

h3. Indicaţii de rezolvare
 
Această problemă este o aplicaţie la 'fluxul maxim de cost minim':http://infoarena.ro/problema/fmcm, graful trebuind să suporte anumite modificari inainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa si destinaţia fluxului) $S$ şi $D$. Vom trage o muchie 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 negative, trebuie aplicat algoritmul Bellman-Ford, soluţia având astfel complexitate $O(FLUX*N*M)$. O astfel de abordare obţine 50 de puncte. Pentru punctaj maxim, trebuie folosită o coadă la implementarea Bellman-Ford-ului. De observat că deşi teoretic aceşti algorimti se comportă destul de prost, în practica vor rula mult mai bine.
 
În cazul problemelor când cuplajul maxim va fi $min(L,R)$, se recomanda 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ă.
 
h3. Aplicaţii
 
Infoarena - 'Adapost':www.infoarena.ro/problema/adapost

...

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