Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rmvc.in, rmvc.out | Sursă | Algoritmiada 2013, Runda Finala |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Return of the MVC
Finalizăm trilogia MVC de anul acesta prin următoarea problemă: Fie un graf G cu N noduri şi M muchii. Numim acoperire cu noduri a grafului o mulţime de noduri A cu proprietatea că orice muchie din graf are cel puţin unul din capete situat in mulţimea A. În această problemă trebuie să găsiţi o acoperire cu noduri a grafului G de cardinal minim.
Se garantează ca pentru grafurile date în input, există o acoperire de noduri cu dimensiune maxim 18.
Date de intrare
Fişierul de intrare rmvc.in conţine pe prima sa linie numerele N şi M semnificând numărul de noduri şi numărul de muchii ale grafului. Următoarele M muchii conţin câte o pereche x y semnificând că există o muchie între nodul x şi nodul y. Se garantează că nu există muchii cu capetele în acelaşi nod, însă pot exista muchii duble.
Date de ieşire
Prima linie a fişierului rmvc.out va conţine dimensiunea acoperirii găsite. Cea de a doua linie va conţine nodurile din acoperire afişate în orice ordine. Orice soluţie de cardinal minim este acceptată.
Restricţii
- 1 ≤ N ≤ 60
- 1 ≤ M ≤ 190
Exemplu
| rmvc.in | rmvc.out |
|---|---|
| 5 6 1 2 1 3 1 4 2 3 2 4 3 4 | 3 3 4 2 |
Explicaţie
...
