Fişierul intrare/ieşire:ccm.in, ccm.outSursăGrigore Moisil 2010, Clasele 11-12
AutorMarius StroeAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inccm.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content