Elérkezett az éves „Varázslók Napja” Ünnepély. A varázslók szervezete ez alkalomból fesztivált szervez. A fesztivál szerte az országban párhuzamosan több helyszínen (városban) zajlik. A fesztivál fő attrakciója egy varázslónak a fellépése, így csak ott lehet fesztivál, ahol egy varázsló megjelenik. Adott a fesztiválra alkalmas helyszínek listája, és a varázslók, akik hajlandók a fesztiválokon fellépni. Egy helyszínen csak egyetlen varázsló léphet fel, hogy ne legyen probléma. A varázslók nem szeretnek messzire utazni az otthonuktól, így nem mindegyik városban hajlandók fellépni. Tudjuk, hogy melyik varázsló melyik városba hajlandó elmenni. Feladat párosítsuk össze a helyszíneket és varázslókat, hogy a lehető legtöbb helyszínen lehessen fesztivál.
(A feladat a 2004-es BME International 24-hour Programming Contest programozói verseny D feladatának egyszerűsített változata, honlapcím: http://www.challenge24.org/2009)
Elsőként megadjuk a varázslók számát (m), majd a városok számát (n). Mind a varázslókat, mind a helyszíneket egy-egy egész számmal azonosítjuk, 0-tól egyesével folyamatosan növekvő azonosítót kapnak. A következő adat (k) mondja meg, hogy hány adatunk van arról, hogy melyik varázsló, melyik városba hajlandó elmenni, majd számpárok formájában (varázsló, város) a varázslók megkötései, pontosan k darab.
Mondjuk meg, hogy mi a maximális száma a megrendezhető fesztiváloknak, és melyik varázsló melyik városba kell menjen.
|
Bemenet: |
Kimenet: |
|
4 4 7 0 2 0 3 1 2 2 0 2 1 3 0 3 3
|
4 0 3 1 2 2 1 3 0 |
Néhány link a magyar módszerhez:
http://www.math.u-szeged.hu/~hajnal/courses/grafelmelet/magyar.htm
http://turul.banki.hu/wp-content/uploads/2008/11/magyar_modszer.ppt
http://www.gdf.hu/html/Magyar_Tudomany_Napja/2008/KS.pdf