O metoda de rezolvare foloseste algoritmii de flux maxim:
Se construieste un graf $G'$ pornind de la graful $G$ la care mai adaugam doua noduri: o sursa si o destinatie. Toate nodurile multimii $A$ se leaga de sursa respectiva si toate nodurile multimii $B$ se leaga de destinatia respectiva. Se considera ca muchiile grafului $G'$ au capacitatea $1$. Valoarea cuplajului maxim in graful $G$ este numeric egala cu valoarea fluxlui maxim din graful $G'$.

O solutie mai rapida si mult mai usor de implementat este cea care se bazeaza pe lanturi augmentative:
Pentru orice $i$ din $A$ definim R~i~ ca fiind nodul de care este acesta cuplat in $B$. De asemenea, pentru orice nod $i$ din $b$, definim L~i~ ca fiind nodul de care este acesta cuplat in $A$. Initial, vectorii au valoarile $0$.
Pentru fiecare nod necuplat din $A$ apelam functia recursiva $pairup$ care va functiona astfel:
1. daca exista un vecin necuplat de-ai lui $i$ ({$R~i~ = 0$}), il vom cupla cu acesta;
2. daca nu, incercam sa fortam cuplarea lui $i$ cu un vecin $j$ deja cuplat (daca se poate), decupland-ul pe acesta si incercand sa recuplam nodul de care era anterior legat. vom apela din nou functia $pairup$, de data aceasta pentru {$L~j~$}, si reluam de la punctul $1$.
La final, valoarea *cuplajului maximal* va fi egala cu numarul de noduri ~i~ cuplate, adica pentru care $R~i~ > 0$.
 
Pentru clarificarea algoritmului puteti consulata "":sursa.

O solutie mai rapida si mult mai usor de implementat

Mai multe detalii despre *cuplajul in graf bipartit*, precum si probleme asemanatoare se pot gasi in acest "aritcol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2.

Bogdan: cosmine in primul rand nu terminasem problema. normal ca pun solutia smechera, doar am dat N < 2000 :). La flux1 si flux2 am vorbit si cu alti membri infoarena care mi-au sugerat sa fac in doua probleme. am inteles ca azi (03.03.2008) discutati arhiva educationala. daca se hotaraste ceva o sa schimb precum se decide.
 
Cosmin: bogdane nu imi place ca faci 3 probleme care ar fi putut fi bagate in aceiasi: flux. Daca tot ai facut problema de cuplaj zi solutia misto cu recursivitate care se scrie foarte scurt si algoritmul de cuplaj in O(sqrt(n) * m).
 
Eu as face din primele 2 probleme de flux una singura. Cu ford fulkerson sa se ia 50 de puncte si cu dinic 100.
 
Nu e bine sa bagi material mult daca nu e nou, asa numa spamezi arhiva educationala ... si ajunge la fel de greu de folosit ca si cea mare.
 

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