Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose there is a city,the city has N buildings. In fact, any building in this city is either A HOUSE or A RESTAURANT. The N buildings are conveniently numerated by integer numbers from 1 to N. To move from some building to others, there are M two-way roads. Each road connects two buildings.It is possible that there are several roads that connect the same pair of buildings, but there won't be a road that connects a building to itself. The Chief Minister of that city wants to make the ways to the restaurants more interesting. To do that he is going to decorate some roads. Each road has its own integer cost of decorating. Some costs may be negative. "If the cost is negative Chief Minister will get some reward for decorating this road. "Now Chief Minister doesn't have much money (small budget)so he wants to decorate roads in such a way that FROM EACH HOUSE, AT LEAST ONE RESTAURANT IS REACHABLE USING ONLY DECORATED ROADS.The total cost of decorated roads should be minimal. So, our task is to help Chief Minister to calculate the minimal cost of any satisfactory subset.The answer can be negative also ,if minister rewards for decorating some roads are greater than his spent money. *EXAMPLES*

Example 1:

When N=3 and M=5

Building 1=House ,Bulding 2=House and Building 3=Restaurant

1 2 3(road that connects buildings 1 and 2 with the cost of decorating equal to 3)

1 2 5(road that connects buildings 1 and 2 with the cost of decorating equal to 5)

1 3 10(road that connects buildings 1 and 3 with the cost of decorating equal to 10)

3 2 -1(road that connects buildings 3 and 2 with the cost of decorating equal to -1)

3 1 7(road that connects buildings 3 and 1 with the cost of decorating equal to 7) In this case ANSWER=2

Example 2: N=2 and M=2

Building 1=Restaurant and Bulding 2=Restaurant

(Xi Yi Zi)

a road that connects buildings Xi and Yi with the cost of decorating equal to Zi.

1 2 1

2 1 2


Example 3:

N=3 and M=3

Building 1=House ,Bulding 2=Restaurant and Building 3=Restaurant

(Xi Yi Zi)

1 2 1(a road that connects buildings Xi and Yi with the cost of decorating equal to Zi.)

1 3 2

2 3 3


What is the efficient technique(algorithm )to solve this problem?

*The question is modified a bit in order to show importance of Negative costs.

share|cite|improve this question
So if I understand you right, you collapse all the "restaurants" to a single node and then want to find a minimum spanning tree? – Carl Jan 5 '12 at 19:04
This is an application of Dijkstra's Algorithm. Of note, you can simplify multiple path's between two buildings into the one path with the least cost. Clearly, you will need to decorate one road per house at a minimum. – Joshua Shane Liberman Jan 5 '12 at 19:09
@carl::Please Can you elaborate it...I dont think the approach you suggested produces the correct answer.(as per the given xamples in the problem statement). – user22394 Jan 5 '12 at 19:16
@ Joshua Shane Liberman::I don't think Dijkstra's will wrk for the given problem as Dijkstra's algo does not work with negative distances(costs).. – user22394 Jan 5 '12 at 19:24
@Aman kumar Choosing which roads to decorate is not affected if you add cost uniformly to every edge to make the entire graph non-negative. In practice however, the non-positive edges will always be decorated because they reduce cost. You only have to worry about the positive edges and houses that are left. – Joshua Shane Liberman Jan 5 '12 at 19:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.