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 16.
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 duble sau muchii cu capetele în acelaşi nod.
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.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| rmvc.in | rmvc.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
