Feladatok‎ > ‎

Csatornatisztító robot

Ihlet- és bemenetforrás: mester.inf.elte.hu

Leírás

Egy vállalat csatornatisztító robotok üzemeltetésével foglalkozik. Szeretnének üzembe helyezni egy szennyvízcsatorna-tisztító robotot Budapest csatornáiban. Viszont a város csatornahálózata nagyon bonyolult, ezért megkértek minket, hogy írjunk egy programot, ami segít nekik eligazodni.

A csatornahálózat N darab csomópontból áll, amiket az 1, 2, … N számokkal azonosítunk. A csomópontok között csatornaszakaszok húzódnak (összesen M darab), és mindegyiknek ismert a keresztmetszete. Mivel egy termetesebb robotról van szó, nem fér bele a legkisebb lyukakba, csak azokon a csatornaszakaszokon tud végighaladni, amiknek a keresztmetszete legalább K.

Írjunk programot, ami kiszámítja, hogy legalább hány helyről kell elindítaniuk a robotot, hogy minden csomópontot érinthessen.

Bemenet

Az első sor N-et, M-et és K-t tartalmazza szóközzel elválasztva. Az ez utáni M sor egy-egy csatornaszakaszról árulja el a két végpontját, illetve a keresztmetszetét (ilyen sorrendben, szóközzel elválasztva).

Kimenet

A kimenet egyetlen szám, mégpedig hogy hány helyről kell minimum elindítani a robotot, hogy minden csomópontba eljuthasson.

Segítség

ċ
be1.txt
(0k)
Bence Hornák,
2017. máj. 12. 1:21
ċ
be2.txt
(130k)
Bence Hornák,
2017. máj. 12. 1:21