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
ANSWER=0
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
ANSWER =1
What is the efficient technique(algorithm )to solve this problem?
*The question is modified a bit in order to show importance of Negative costs.