Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 79. feladat (2013. március)

S. 79. Adott egy súlyozott N csúcsú, M élű gráf: N\le 100\;000, M\le 100\;000. Adjuk meg minden e élre, hogy létezik-e e-t tartalmazó minimális feszítőfa. Minimális feszítőfának egy minimális összsúlyú feszítőfát nevezünk. Feszítőfa egy olyan fa, mely a gráf összes csúcsát, illetve az éleinek egy részhalmazát tartalmazza. Fának pedig egy olyan gráfot nevezünk, mely körmentes. Egy minimális feszítőfa tartalmazza e-t, ha egy olyan minimális feszítőfa, melynek az e az egyik éle. A program olvassa be a standard input első sorából N-et és M-et, majd a következő M sorból a ki, vi, si szóközzel elválasztott egészeket: azaz a ki kezdőpontú, vi végpontú, si súlyú éleket, és írja a standard output i-edik sorába az ,,Igen'' szót, ha létezik olyan minimális feszítőfa, mely az i-edik élet tartalmazza, és a ,,Nem'' szót, ha nem létezik ilyen.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül. Kapható részpontszám a 9 pontból, ha a program csak kisebb tesztesetekre tud lefutni időben. Az alábbi korlátok érvényesek az egyes részmegoldásokra:

\bullet 2 pontért: 0<M\le300;

\bullet további 3 pontért: 300< M\le 2\;000;

\bullet további 4 pontért: 2\;000< M\le 100\;000.

Beküldendő egy tömörített s79.zip állományban a program forráskódja (s79.pas, s79.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s79.txt, s79.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2013. április 10-én LEJÁRT.


Megoldás

Lassú megoldás A Kruskal algoritmussal először besszük a kérdéses élet, majd utána a Kruskallal folytatjuk. Ezt minden élre külön külön eljátsszuk, ez azt jelenti, hogy mindne élre egy külön Kruskalt kell futtatnunk, viszont egyszerű, és nyilván jó megoldást ad.

Gyors, mlogn-es megoldás Azaz pont a Kruskal futásideje a megoldás futásideje is. Az az alapötlet, hogy a Kruskalt futtatjuk, csak épp nem a következő élről döntjük el, hogy bevesszük-e, hanem a következő kupac élről. Először pedig az összes élet kupacokba osztjuk, úgy, hogy egy kupacban az azonos súlyúak legyenek. Az általános lépésben a következő kupacot kell feldolgozni. ELőször minden élről eldöntjük, hogy be lehetne-e venni, azaz a két végpontja nem egy komponensben van-e. Ha be lehetne venni a feszítőfába, akkor kiírjuk. Ezután és csakis az egész kupac végignézése után újrakezdjük a végignézését a kupacnak, csak most valóban be is vesszük, ha nem okoz kört. Most már csak be kell bizonyítani, hogy ez így valóban megadja az összes olyan élet, ami szerepelhet egy minimális feszítőfában. Nyilván csak olyanokat adhat meg, ami szerepelhet, belátjuk, hogy az összes ilyet megadja: vegyünk egy s súlyú élet, és egy hozzá tartozó minimális feszítőfát. Ekkor az s-nél kisebb súlyú élek által alkotott összefüggőségi komponenseket a Kruskal során megkaptuk már. És akkor pont azt adja meg az algoritmus, hogy egy ilyen komponensben van-e ez az s súlyú él, vagy két komponens között vezet.

A Kruskal algoritmusról a Wikipedián lehet olvasni.

A mintamegoldás unióholvan adatszerkezettel (tehát gyorsan): main.cpp


Statisztika:

6 dolgozat érkezett.
10 pontot kapott:Szabó 928 Attila, Vályi András.
2 pontot kapott:2 versenyző.
0 pontot kapott:2 versenyző.

A KöMaL 2013. márciusi informatika feladatai