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

×

RHOUSE - Editorial

1
2

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Obviously, all the roads that will be profitable should be decorated. So we will include them in the answer at the very beginning. Then we can sort the rest of edges by their cost and apply the following greedy approach: if the edge connects two connected components and there is no restaurant in at least one of these components then this edge should be included into the answer and the components should be merged. Merging components can be done by union-find data structure. Another similar approach is to connect all the restaurants in the very beginning, after including the edges with negative weight and simply build a mst then. Also pay attention that the upper bound of the answer may fit into int but the lower bound of the answer could be about -8*10^9 so 64-bit type should be used for storing the answer(long long in C++, int64 in Pascal).

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 22 Nov '12, 12:17

admin's gravatar image

0★admin ♦♦
15.4k347484505
accept rate: 35%


What is the o/p of the following case?

1 
4 3 
HRHR 
1 2 3 
2 3 2 
3 4 -1

My AC solution is giving 2, but i think it is 4.

link

answered 10 Mar '15, 17:53

krishnaanaril's gravatar image

3★krishnaanaril
11
accept rate: 0%

edited 10 Mar '15, 17:54

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:

×10,863
×2,522
×8
×2

question asked: 22 Nov '12, 12:17

question was seen: 3,170 times

last updated: 10 Mar '15, 17:54