How to solve road repair problem from SPOJ?

Please provide detailed explanation on how to solve IITWPC4I - Petya and Repairment of Roads from spoj.

Read this carefully ->>> "Note that a milkmen does not need to go to some other milkmen for milk as he can take milk from his own home. ". Now we can connect milkmen with a zero weight edge and calculate MST of the resulting answer. In this way each home will be connected to a milkmen with minimum cost.
Hope it helps!

1 Like

Kruskal’s algorithm will do the trick.


why can’t we simply ignore edges between two milkmen.

@vikram91 @rs_710 @purendra_ @hemanth_1 @shraeyas @vidyut_1 @aryanc403 @meooow @alexthelemon @vijju123 @ram_24 @harrypotter0 @pankaj_chopra guys please help.


I am getting wrong answer, my solution Petya and Repairment of Roads -


Updated solution road repairment -


Can you please look into it.