×

# How to solve road repair problem from SPOJ?

 0 Please provide detailed explanation on how to solve IITWPC4I - Petya and Repairment of Roads from spoj. asked 05 Apr '18, 08:10 1★arpit728 683●15●63 accept rate: 10% (25 Apr '18, 11:24) arpit7281★ @vivek_1998299 Can you please look into it. (03 May '18, 09:36) arpit7281★

 0 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 195●8 accept rate: 7% why can't we simply ignore edges between two milkmen. (11 Apr '18, 23:20) arpit7281★
 0 Kruskal's algorithm will do the trick. answered 25 Apr '18, 12:20 3★shraeyas 1.3k●2●6●18 accept rate: 10% I am getting wrong answer, my solution https://pastebin.com/VDEdpnS8 (25 Apr '18, 22:23) arpit7281★ @shraeyas Updated solution https://pastebin.com/iw2Mz7xD (26 Apr '18, 00:17) arpit7281★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,197
×114
×72

question asked: 05 Apr '18, 08:10

question was seen: 717 times

last updated: 03 May '18, 09:36