4 5 10 2 1 7
|

h3. Indicaţii de rezolvare

h2. 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.

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 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ă.

Î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ă.

h3. Aplicaţii

h2. Aplicaţii

Infoarena - 'Adapost':www.infoarena.ro/problema/adapost

Infoarena - 'Adapost':http://www.infoarena.ro/problema/adapost
Infoarena - 'Traseu':http://www.infoarena.ro/problema/traseu
Infoarena - 'Trafic':http://www.infoarena.ro/problema/trafic
Infoarena - 'Cc':http://infoarena.ro/problema/cc
SGU - '252':http://acm.sgu.ru/problem.php?contest=0&problem=252

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