D. Power Plant
Author: Suhendry Effendy
(link to problem D)
To solve this problem, let us construct a graph G’ which is equivalent to the original graph G, but also contains an additional node x and edges (x,y) with zero weight for all nodes y in G which are power plants. Find the MST of G’ and this is the answer to the problem.
Figure 1 shows an example of graph G’ while the area enclosed by the red box is the original graph G. Figure 2 shows the MST of G’ and the cost of this MST is equal to the answer to this problem.
To understand why this solution works, first, notice that all nodes in T’ (the MST of G’) are connected to node x, and node x only connected to power plants in G’. If we remove x from T’, then all the remaining nodes are still connected to the power plants. Therefore, T’ is a valid (feasible) solution to the problem. Moreover, T’ has the minimum cost since the edges connecting x to the power plants have zero weight.