Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cuplaj1.in, cuplaj1.out | Sursă | |
| Autor | Autor necunoscut | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cuplaj Maxim
Se numeste graf bipartit un graf G ale carui noduri pot fi partitionate in doua multimi disjuncte A si B astfel incat oricare muchie contecteaza un nod din A si un nod din B. Cu alte cuvinte, nu exista doua nudori i si j din aceeasi multime astfel incat sa existe muchie intre ele.
Fie G un graf bipartit. Numim cuplaj o submultime de noduri 
cu proprietatea ca ∀ i ∈ M exista un unic j ∈ B astfel incat intre i si j sa fie muchie. Numim cuplaj maxim o multime M de cardinal maxim, adica nu exista nicio alta multime M' cu |M'| > |M| (unde cu |M| am notat cardinalul multimii M).
Cerinta
Se da un graf bipartit G. Se cere sa se gaseasca valoarea cuplajului maxim.
Date de intrare
Pe prima linie a fisierului de intrare cuplaj1.in se afla N1, N2 si M. N1 reprezinta numarul de noduri ale multimii A, iar N2 numarul de noduri ale multii B. Pe urmatoarele M linii se afla cate doua numere a si b cu semnificatia ca intre nodurile a ∈ A si b ∈ B exista muchie.
Date de iesire
In fisierul de iesire cuplaj1.out se va scrie o singura valoare, cardinalul cuplajului maxim.
Restrictii
- 1 ≤ N1, N2 ≤ 1000
- 1 ≤ M ≤ 200 000
- nodurile multimii A sunt numerotate de la 1 la N1
- nodurile multimii B sunt numerotate de la 1 la N2
Exemplu
| cuplaj1.in | cuplaj1.out |
|---|---|
| 5 4 6 1 1 2 1 1 4 3 2 5 4 4 2 | 3 |
Indicatii
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'.
Mai multe detalii despre cuplajul in graf bipartit, precum si probleme asemanatoare se pot gasi in acest aritcol.
