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 uneste un nod din A si un nod din B. Cu alte cuvinte, nu exista doua nuduri i si j din aceeasi multime astfel incat sa existe muchie intre ele.
Fie G un graf bipartit. Numim cuplaj o submultime de muchii 
cu proprietatea ca ∀ i ∈ V exista cel mult o muchie in M incidenta in i. Spunem ca i este cuplat de cuplajul M daca exista o muchie in M incidenta in i. In caz contrar 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 un singur numar, valoarea 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.
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.
