Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ccm.in, ccm.out | Sursă | Grigore Moisil 2010, Clasele 11-12 |
| Autor | Marius Stroe | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
CCM
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.
Cerinţă
Dându-se un graf neorientat bipartit G să se determine numărul cuplajelor de cardinalitate maximă.
Date de intrare
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.
Date de ieşire
Î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.
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.
Exemplu
| ccm.in | ccm.out |
|---|---|
| 3 2 5 1 1 1 2 2 1 2 2 3 2 | 2 4 |
Explicaţie
Cele patru cuplaje maxime sunt (1 1) (2 2), (1 1) (3 2), (1 2) (2 1) şi (2 1) (3 2).
