Cuplaj maxim in graf bipartit

Cuplaj maxim în graf bipartit

== include(page="template/taskheader" task_id="cuplaj") ==

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ă.

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ă.

h2. Cerința

h2. Cerinţa

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

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

h2. 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$.

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$.

h2. Date de ieșire

h2. 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$.

Î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$.

h2. Restricții

h2. 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^6^$
* Pentru determinarea corectă a $cuplajului maxim$ se va acorda $40%$ din punctaj și încă $60%$ dacă s-a determinat o submulțime $M$ validă.

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

h2. Exemplu

5 4
|

h3. Explicații

h3. Explicaţii

!problema/cuplaj?Cuplaj.png!

!problema/cuplaj?Cuplaj.png 50%!

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

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

h2. Indicații de rezolvare

h2. Indicaţii de rezolvare

O scurtă lecție de teorie găsiți 'aici':http://en.wikipedia.org/wiki/Maximum_matching și în cartea _Introducere in algoritmi_, Thomas Cormen, editura Agora, Cluj-Napoca.
O soluție exponențială cu metoda $backtracking$ poate fi găsită ușor.
O soluție <tex> O(VE) </tex> cu '$algoritmul lui Edmonds Karp$':http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm se găsește 'aici':job_detail/225136?action=view-source
O soluție ce folosește $lanțuri altenante$ în complexitate <tex> O(VE) </tex> se găsește 'aici':job_detail/225128?action=view-source. Menționez că acest algoritm se comportă foarte bine în practică.
Soluția de $100p$ se obține cu ajutorul '$algoritmului lui Hopcroft Karp$':http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm de complexitate <tex> O(\sqrt{V}E) </tex> ș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':job_detail/225121?action=view-source
În grafuri bipartite, $cuplajul maxim$ este egal cu acoperirea minimă cu noduri ({$minimum$} '$vertex cover$':http://en.wikipedia.org/wiki/Vertex_cover). Din acest rezultat deducem că acoperirea minimă cu noduri ({$minimum vertex cover$}) și multimea maximă de puncte independente ({$maximum$} '$independent set$':http://en.wikipedia.org/wiki/Maximum_independent_set) se pot rezolva în '$timp polinomial$':http://en.wikipedia.org/wiki/Polynomial_time în grafuri bipartite.

O scurtă lecţie de teorie găsiţi pe 'wikipedia':http://en.wikipedia.org/wiki/Maximum_matching şi în cartea '_Introducere in algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm, 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$':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow, 'secţiunea $2$':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2.
O soluţie exponenţială cu metoda $backtracking$ poate fi găsită uşor.
O soluţie <tex> O(VE) </tex> cu 'algoritmul lui Edmonds Karp':http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm se găseşte 'aici':job_detail/225136?action=view-source.
O soluţie ce foloseşte $lanţuri alternante$ în complexitate <tex> O(VE) </tex> se găseşte 'aici':job_detail/225128?action=view-source. Menţionez că acest algoritm se comportă foarte bine în practică.
Soluţia de $100p$ se obţine cu ajutorul 'algoritmului lui Hopcroft Karp':http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm de complexitate <tex> O(\sqrt{V}E) </tex> ş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':job_detail/225121?action=view-source.
În grafuri bipartite, $cuplajul maxim$ este egal cu acoperirea minimă cu noduri (minimum 'vertex cover':http://en.wikipedia.org/wiki/Vertex_cover). Din acest rezultat deducem că acoperirea minimă cu noduri şi multimea maximă de puncte independente ('maximum independent set':http://en.wikipedia.org/wiki/Maximum_independent_set) se pot rezolva în 'timp polinomial':http://en.wikipedia.org/wiki/Polynomial_time în grafuri bipartite.

h2. Probleme suplimentare:
* 'Felinare':problema/felinare
* 'Gandaci Java':problema/java
* 'Paznici':problema/paznici

* 'Taramul Nicaieri':problema/harta
* 'Knights':http://iskren.info/info-arh/BalticOI/2001/blue-a4.ps, BalticOI 2001

* 'Senat':problema/senat
* 'Knights':http://iskren.info/info-arh/BalticOI/2001/blue-a4.ps, _BalticOI 2001_

* 'Beloved Sons':http://acm.sgu.ru/problem.php?contest=0&problem=210
* 'Unstable Systems':http://acm.sgu.ru/problem.php?contest=0&problem=218
* 'Black-White King Strikes Back':http://acm.sgu.ru/problem.php?contest=0&problem=234

* 'Euler Circuit':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1676
* 'Gopher Strategy':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1745
* 'Royal Guards':http://ics.upjs.sk/ceoi/documents/tasks/guards-tsk.pdf, CEOI 2002

* 'Euler Circuit':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1676
* 'Gopher Strategy':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1745
* 'Royal Guards':http://ics.upjs.sk/ceoi/documents/tasks/guards-tsk.pdf, _CEOI 2002_

* 'Muddy Fields':http://www.spoj.pl/problems/MUDDY/
== include(page="template/taskfooter" task_id="cuplaj") ==