LC: 1168. Optimize Water Distribution in a Village - spiralgo/algorithms GitHub Wiki

1168. Optimize Water Distribution in a Village:

The Essence:

  • We can interpret this question as a graph problem and solve the problem using an MST (minimum spanning tree) algorithm:

Given a connected, edge-weighted and undirected graph, a minimum spanning tree is a subset of edges that connect all vertices while the total weights of these edges are minimum among all possible subsets.

  • But there is one major difference between a usual graph and our problem structure here. In our problem, not just edges but also every vertex has a cost weight.

  • To mitigate this gap, we can imagine a virtual vertex, like in the picture above. We can assume that the virtual vertex is the water source.

image

Details:

There are several algorithms for MST problems.

But we have a detailed PR for the most popular ones: Prim's algorithm and Kruskal's algorithms here: https://github.com/spiralgo/algorithms/pull/365