== include(page="template/taskheader" task_id="ccm") ==
Poveste şi cerinţă...
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 orice vârf $v$ din $V$, există cel mult o muchie în $M$ incidentă în $v$.
h3. Cerinţă
Dându-se un graf neorientat bipartit $G$ să se determine numărul cuplajelor de cardinalitate maximă.
h2. Date de intrare
Fişierul de intrare $ccm.in$ ...
Fişierul de intrare $ccm.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 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
În fişierul de ieşire $ccm.out$ ...
În fişierul de ieşire $ccm.out$ veţi afişa două valori separate printr-un spaţiu, reprezentând valoarea cuplajului de cardinalitate maximă şi numărul acestora modulo $9901$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n, m ≤ 16$
* $1 ≤ e ≤ n * m$
* Nodurile din mulţimile $L$, $R$ sunt reprezentate de numere naturale de la $1$ la $n$, respectiv de la $1$ la $m$.
h2. Exemplu
table(example). |_. ccm.in |_. ccm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2 5
1 1
1 2
2 1
2 2
3 2
| 2 4
|
h3. Explicaţie
...
Cele patru cuplaje maxime sunt $(1 1) (2 2)$, $(1 1) (3 2)$, $(1 2) (2 1)$ şi $(2 1) (3 2)$.
== include(page="template/taskfooter" task_id="ccm") ==
