PROBLEM LINK:
Author: tseccodecell
DIFFICULTY:
Medium
PREREQUISITES:
PROBLEM:
You are given a network of cities with roads to be repaired between them. The task is to make at least one shop accessible to all cities, while minimizing the cost for doing so. There is a fixed cost croad for fixing one road and a fixed cost cshop for constructing a shop in one city.
QUICK EXPLANATION:
If cshop<=croad, solution is trivial (noofcities*cshop). Otherwise, construct a disjoint set data structure for the graph. If number of disjoint set forests is count, minimum cost is croad*(noofcities-count)+cshop*count.
EXPLANATION:
Suppose cshop<=croad. In this case, cost of constructing a road to connect to another city with a shop is more than cost of constructing a shop in your own city. So the optimal solution is to construct a shop in all cities.
Suppose cshop>croad. In this case, constructing roads to connect all cities possible becomes more optimal. First we find use a disjoint set (union find) data structure to find number of disjoint set forest in the graph (road network). For each disjoint set, we construct one shop in any city and find minimum spanning tree for it. However since all edges (roads) of the graph have same cost, all spanning trees will have same total cost. Consider a connected graph of n cities. (Minimum) Spanning tree will have (n-1) roads. If we delete any one road, we get 2 disjoint sets and total (n-2) roads. We find that number of roads in the graph is (noofcities-no_of_disjoint_sets). If number of disjoint set forests is count:
Total cost for shops=cshop*count
Total cost for roads=croad*(noofcities-count)
Total cost=cshop*count+croad*(noofcities-count)