×

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, 08:10 2★arpit728 683●12●53 accept rate: 10% (25 Apr, 11:24) arpit7282★ @vivek_1998299 Can you please look into it. (03 May, 09:36) arpit7282★

 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, 22:14 185●7 accept rate: 7% why can't we simply ignore edges between two milkmen. (11 Apr, 23:20) arpit7282★
 0 Kruskal's algorithm will do the trick. answered 25 Apr, 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, 22:23) arpit7282★ @shraeyas Updated solution https://pastebin.com/iw2Mz7xD (26 Apr, 00:17) arpit7282★
 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,158
×96
×72