h2. Indicaţii de rezolvare

Această problemă este o aplicaţie la problema mai generală 'fluxul maxim de cost minim':problema/fmcm, aici graful trebuind să suporte anumite modificări înainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa şi destinaţia fluxului) $s$ şi $d$. Vom adăuga 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':problema/fmcm din această reţea. Datorită existenţei muchiilor de cost negativ, trebuie aplicat algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, soluţie ce are ordinul de execuţie $O(FLUX*N*M)$, cu $FLUX$ reprezentând cardinalul cuplajului maxim. 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?action=view-source. Pentru punctaj maxim, trebuie implementat algoritmul Bellman-Ford cu coadă (o sursă doar a acestui algoritm se găseşti 'aici':job_detail/184224?action=view-source). Această implementare se poate găsi 'aici':http://infoarena.ro/job_detail/371534?action=view-source. De observat că deşi teoretic aceşti algoritmi necesită un timp mare de execuţie, în practică se comportă mult mai bine.

Această problemă este o aplicaţie la problema mai generală a 'fluxului maxim de cost minim':problema/fmcm, aici graful trebuind să suporte anumite modificări înainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa şi destinaţia fluxului) $s$ şi $d$. Vom adăuga 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':problema/fmcm din această reţea. Datorită existenţei muchiilor de cost negativ, trebuie aplicat algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, soluţie ce are ordinul de execuţie $O(FLUX*N*M)$, cu $FLUX$ reprezentând cardinalul cuplajului maxim. 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?action=view-source. Pentru punctaj maxim, trebuie implementat algoritmul Bellman-Ford cu coadă (o sursă doar a acestui algoritm se găseşti 'aici':job_detail/184224?action=view-source). Această implementare se poate găsi 'aici':http://infoarena.ro/job_detail/371534?action=view-source. De observat că deşi teoretic aceşti algoritmi necesită un timp mare de execuţie, în practică se comportă mult mai bine.

Î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 pe 'infoarena':algoritm-kuhn şi pe 'wikipedia':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ă.

Dacă graful $G$ nu are costuri pe muchii atunci problema se reduce la 'cuplajul maxim în graf bipartit':problema/cuplaj.

Dacă graful $G$ are toate muchiile de cost egal, atunci problema se reduce la 'cuplajul maxim în graf bipartit':problema/cuplaj.

h2. Aplicaţii