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

Se dă un graf neorientat bipartit $G(V=(L,R),E)$ cu costuri pe muchii. Definim un cuplaj in graf ca fiind o submulţime de muchii $M ⊂ E$, cu prorietatea că pentru orice nod $v$ din $V$, va exista cel mult o muchie în mulţimea $M$ incidentă in $v$. Costul unui cuplaj este determinat de suma costurilor muchiilor care îl compun.

Se dă un graf neorientat bipartit $G(V=(L,R),E)$ cu costuri pe muchii. Definim un cuplaj în graf ca fiind o submulţime de muchii $M ⊂ E$, cu prorietatea că pentru orice nod $v$ din $V$, va exista cel mult o muchie în mulţimea $M$ incidentă în $v$. Costul unui cuplaj este determinat de suma costurilor muchiilor care îl compun.

h2. Cerinţă

Pentru un graf $G$, să se determine cuplajul de cardinal maxim si cost minim.

Pentru un graf $G$, să se determine cuplajul de cardinal maxim şi cost minim.

h2. Date de intrare

Pe prima linie a fişierului de intrare $cmcm.in$ se vor găsi trei numere $N,M$ şi $E$, reprezentând cardinalul muţimii $L$, cardinalul mulţimii $R$, respectiv numărul de muchii din graf. Pe următoarele $E$ linii se vor găsi cate trei numere naturale $P,Q$ si $C$, cu semnificaţia ca există o muchie de la nodul $P$ din $L$ la nodul $Q$ din $R$ de cost $C$.

Pe prima linie a fişierului de intrare $cmcm.in$ se vor găsi trei numere $N$, $M$ şi $E$, reprezentând cardinalul mulţimii $L$, cardinalul mulţimii $R$, respectiv numărul de muchii din graf. Pe următoarele $E$ linii se vor găsi câte trei numere naturale $P$, $Q$ şi $C$, cu semnificaţia că există o muchie de la nodul $P$ din $L$ la nodul $Q$ din $R$ de cost $C$.

h2. Date de ieşire

Pe prima linie a fişierului de ieşire $cmcm.out$ veti afişa două numere $Nr$ si $K$, reprezentând numărul de muchii din cuplajul maxim, precum si costul minim al acestui cuplaj. A doua linie va conţine $Nr$ numere reprezentând indicii muchiilor folosite pentru construcţia cuplajului soluţie.

Pe prima linie a fişierului de ieşire $cmcm.out$ veţi afişa două numere $Nr$ şi $K$, reprezentând numărul de muchii din cuplajul maxim, precum şi costul minim al acestui cuplaj. A doua linie va conţine $Nr$ numere reprezentând indicii muchiilor folosite pentru construcţia cuplajului soluţie.

h2. Restricţii
* $1 ≤ N, M ≤ 300$
* $1 ≤ E ≤ 50 000$
* $-20 000 ≤ C ≤ 20 000$

* Indicii muchiilor se pot afişa în orice ordine
* În caz că există mai multe soluţii puteţi afişa oricare

* Indicii muchiilor se pot afişa în orice ordine.
* În caz că există mai multe soluţii o puteţi afişa pe oricare.

h2. Exemplu

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

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

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

h2. Aplicaţii

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

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

h2. Aplicaţii
* 'Adapost':problema/adapost
* 'Traseu':problema/traseu
* 'Trafic':problema/trafic
* 'Cc':problema/cc
* 'Railway Communication':http://acm.sgu.ru/problem.php?contest=0&problem=252, sgu

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

4346