Gáspár Attila
12. o. t.
Földes F. Gimn., Miskolc
Fejlesztőkörnyezet: Visual C++ 2013 Express

A gráfot úgy járjuk be, hogy ha egy csúcsba bemegy a busz, akkor a részfájából a lehető legtöbb utast elszállítja, és amikor később megint bejárjuk, akkor legfeljebb 1 utast tudunk a részfából elszállítani. Ha egy csúcsban kevés utas van, akkor nézzük meg, hogy a csúcsnak melyik gyerekeiből lehet a legtöbb utast elszállítani. Ha sok utas van, akkor az összes gyerekéből szállítsuk el a lehető legtöbb utast, végezzük el a lehető legtöbb második bejárást, és számoljuk ki, hogy még hány további bejáráskor lehet egy-egy utast elszállítani.
Az algoritmus futásideje O(M * log(U)).