You are not logged in. Please login at to post your questions!


How to solve road repair problem from SPOJ?

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

asked 05 Apr '18, 08:10

arpit728's gravatar image

accept rate: 10%


Can you please look into it.

(03 May '18, 09:36) arpit7281★

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!


answered 05 Apr '18, 22:14

amulyagaur111's gravatar image

accept rate: 7%


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

(11 Apr '18, 23:20) arpit7281★

Kruskal's algorithm will do the trick.


answered 25 Apr '18, 12:20

shraeyas's gravatar image

accept rate: 10%


I am getting wrong answer, my solution

(25 Apr '18, 22:23) arpit7281★
(26 Apr '18, 00:17) arpit7281★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 05 Apr '18, 08:10

question was seen: 717 times

last updated: 03 May '18, 09:36