Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | count.in, count.out | Sursă | preONI 2006 Runda 3 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de | |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Count
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
Link: [1]File-List
count
Fiind dat un graf planar cu N noduri si M muchii aflati numarul maxim de noduri pe care il poate avea un subgraf complet al sau (un graf neorientat se numeste complet daca exista muchie intre oricare doua noduri ale sale). De asemenea se cere si numarul de subgrafuri complete cu numar maxim de noduri care se gasesc in graful planar dat.
Cerinta
Fiind dat un graf planar aflati cele doua numere cautate.
Date de Intrare
Linia 1 a fisierului de intrare contine doua numere naturale separate prin spatii N si M (numarul de noduri, respectiv numarul de muchii ale grafului planar).
Liniile 2 .. M + 1 contin cate doua numere A si B cu semnificatia: exista o muchie bidirectionala intre nodurile A si B (nodurile grafului sunt numerotate de la 1 la N).
Date de Iesire
Fisierul de iesire va contine pe prima linie doua numere X si Y reprezentand numarul maxim de noduri pe care il poate avea un subgraf complet si, respectiv, numarul de subgrafuri complete cu X noduri din graful planar dat.
Restrictii si precizari
o 2 <= N <= 30 000
o 1 <= M <= 60 000
o Y <= 2^30
o Pentru 70% din teste N <= 2000
Exemplu
| count.in | count.out | Explicatii |
| 5 8 | 3 4 | Se pot forma 4 subgrafuri complete cu 3 noduri. Acestea sunt: |
| 1 2 | ||
| (1 2 5), (2 4 5), (3 4 5), (1 3 5) | ||
| 1 3 | ||
| 1 5 | ||
| 2 4 | ||
| 2 5 | ||
| 3 4 | ||
| 3 5 | ||
| 4 5 | ||
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/count/enunt.files/filelist.xml
