== 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ă oricărui nod $v$ din $V$ îi va corespunde cel mult o muchie din mulţimea $M$. 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. Pe fiecare din următoarele $Nr$ linii se va găsi un număr $x$, indicând indicele unei muchii 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 ≤ 20 000$
* $-50 000 ≤ C ≤ 50 000$
* Valorie $x$ se vor afişa în ordine crescătoare
* În caz că există mai multe soluţii puteţi afişa oricare

* $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 o puteţi afişa pe oricare.

h2. Exemplu
table(example). |_. cmcm.in |_. cmcm.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 10 12
5 3 5
4 7 -5
5 9 -1
1 2 -1
2 9 5
6 1 0
6 4 -5
3 9 3
4 10 -3
3 8 4
4 8 -5
5 2 6
| 6 3
4 5 10 2 1 7

|

h3. Explicaţie

h2. Indicaţii de rezolvare

...

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$ are toate muchiile de cost egal, atunci problema se reduce la 'cuplajul maxim în graf bipartit':problema/cuplaj.
 
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