Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | gbc.in, gbc.out | Sursă | Summer Challenge 2007, runda 2 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gbc
Fie G = (V, E) un graf neorientat cu V multimea varfurilor, iar E multimea muchiilor. Definim un subgraf bipartit complet bun al lui G un graf G' = (V', E') cu proprietatile urmatoare:
- V' = A U B
- V' ⊆ V
- E' = { (i,j) | i ∈ A, j ∈ B } ( toate muchiile cu un capat in A si celalalt capat in B )
- E' ⊆ E
- |A| = n
- |B| = m
Cerinta
Dandu-se G, un graf neorient conex, se cere sa se determine cate subgrafuri bipratite complete bune are.
Date de intrare
Pe prima linie a fisierului de intrare gbc.in se afla trei numere intregi k - numarul de noduri ale grafului G, n si m - cu semnificatia din enunt. Urmatoarele k linii contin cate k numere 0 sau 1 cu semnficatia ca daca pe linia i+1, pe coloana j se afla 1 atunci avem muchie intre nodurile i si j.
Date de iesire
In fisierul de iesire gbc.out se va scrie pe prima linie numarul de subgrafuri bipratite complete bune ale grafului din fisierul de intrare.
Restrictii
- 1 ≤ n,m ≤ 8
- 1 ≤ k ≤ 30
Exemplu
| gbc.in | gbc.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
