Pagini recente » bellmanford | Monitorul de evaluare | Diferente pentru problema/ciclueuler intre reviziile 6 si 15 | Numerele lui Stirling | Cuplaj maxim in graf bipartit

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-04 13:17:21.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	cuplaj.in, cuplaj.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Lucian Bicsi •retrograd
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Cuplaj maxim in graf bipartit

Se dă un graf neorientat bipartit G = (V = (L, R), E). Un cuplaj în G este o submulţime de muchii M astfel încât pentru toate vârfurile v din V, există cel mult o muchie în M incidentă în v. Un cuplaj maxim este un cuplaj de cardinalitate maximă.

Cerinţa

Dându-se un graf neorientat bipartit G să se determine un cuplaj maxim.

Date de intrare

Fişierul de intrare cuplaj.in conţine pe prima linie trei numere naturale N, M şi E, unde N reprezintă cardinalul mulţimii L iar M cardinalul mulţimii R. Pe următoarele E linii se vor afla câte două numere naturale, separate între ele printr-un spaţiu, u şi v, cu semnificaţia că există muchie de la nodul u din L la nodul v din R.

Date de ieşire

În fişierul de ieşire cuplaj.out veţi afişa pe prima linie un singur număr reprezentând cuplajul maxim. Pe fiecare din următoarele linii veţi afişa câte două numere x şi y, separate între ele prin spaţiu, cu semnificaţia că nodul x din L a fost cuplat cu nodul y din R.

Restricţii

1 ≤ N, M ≤ 10 000
0 ≤ E ≤ minim(100 000, N * M)
Pentru 20% dintre teste: 1 ≤ N ≤ 100, 1 ≤ M ≤ 20
Pentru 50% dintre teste: 1 ≤ (N + M) * E ≤ 5 * 10⁶
Pentru determinarea corectă a cuplajului maxim se va acorda 40% din punctaj şi încă 60% dacă s-a determinat o submulţime M validă.

Exemplu

cuplaj.in	cuplaj.out
5 4 9 1 1 1 2 2 1 2 2 2 3 3 2 4 2 5 2 5 4	4 1 1 2 3 3 2 5 4

Explicaţii

În graful din exemplu se vor cupla următoarele perechi de noduri: (1, 1), (2, 3), (3, 2), (5, 4).

Indicaţii de rezolvare

O scurtă lecţie de teorie găsiţi pe wikipedia şi în cartea Introducere in algoritmi, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Alte articole excelente care tratează problema fluxului maxim pe larg se găsesc la adresele următoare: secţiunea 1, secţiunea 2.
O soluţie exponenţială cu metoda backtracking poate fi găsită uşor.
O soluţie $O(VE)$ cu algoritmul lui Edmonds Karp se găseşte aici.
O soluţie ce foloseşte lanţuri alternante în complexitate $O(VE)$ se găseşte aici. Menţionez că acest algoritm se comportă foarte bine în practică.
Soluţia de 100p se obţine cu ajutorul algoritmului lui Hopcroft Karp de complexitate $O(\sqrt{V}E)$ şi este o îmbunătăţire a soluţiei precedente: la fiecare pas al iteraţiei se găseşte un număr maximal de lanţuri alternante care acceptă o augmentare de o unitate de flux. Această soluţie se găseşte aici.
În grafuri bipartite, cuplajul maxim este egal cu acoperirea minimă cu noduri (minimum vertex cover). Din acest rezultat deducem că acoperirea minimă cu noduri şi multimea maximă de puncte independente (maximum independent set) se pot rezolva în timp polinomial în grafuri bipartite.