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, 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':job_detail/371522. Pentru punctaj maxim, trebuie folosită o coadă la implementarea Bellman-Ford-ului. Această implementare se poate găsi 'aici':job_detail/371534. De observat că deşi teoretic aceşti algoritmi necesită un timp mare de execuţie, în practica se comportă mult mai bine.

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, 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':job_detail/371522. Pentru punctaj maxim, trebuie folosită o coadă la implementarea Bellman-Ford-ului. Această implementare se poate găsi 'aici':job_detail/371534. 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ă.