PROBLEM LINKSDIFFICULTYEASY EXPLANATIONObviously, 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 unionfind 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 64bit type should be used for storing the answer(long long in C++, int64 in Pascal). SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 22 Nov '12, 12:17

What is the o/p of the following case?
My AC solution is giving 2, but i think it is 4. answered 10 Mar '15, 17:53
