You are not logged in. Please login at www.codechef.com 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, 08:10

arpit728's gravatar image

2★arpit728
6831149
accept rate: 10%


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!

link

answered 05 Apr, 22:14

amulyagaur111's gravatar image

4★amulyagaur111
1737
accept rate: 8%

@amulyagaur111

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

(11 Apr, 23:20) arpit7282★

Kruskal's algorithm will do the trick.

link

answered 25 Apr, 12:20

shraeyas's gravatar image

3★shraeyas
1.3k1518
accept rate: 10%

@shraeyas

I am getting wrong answer, my solution https://pastebin.com/VDEdpnS8

(25 Apr, 22:23) arpit7282★
(26 Apr, 00:17) arpit7282★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,123
×93
×71

question asked: 05 Apr, 08:10

question was seen: 256 times

last updated: 03 May, 09:36