RHOUSE - Editorial

editorial
, , ,
1

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.

2 Likes
2

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.

3

The correct answer is 2 only because House 1 will be connected to Restaurant 2 with cost of 3 and House 3 will be connected to Restaurant 4 with cost of -1. So output will be 2.
Note that Restaurant 2 and House 3 need not be connected because we are able to connect all houses to atleast one restaurants.