1168. Optimize Water Distribution in a Village
Union-FindGraph TheoryHeap (Priority Queue)Minimum Spanning TreePrim's AlgorithmKruskal's AlgorithmBorůvka's Algorithm
Hints
Hint 1
What if we model this problem as a graph problem?
Hint 2
A house is a node and a pipe is a weighted edge.
Hint 3
How to represent building wells in the graph model?
Hint 4
Add a virtual node, connect it to houses with edges weighted by the costs to build wells in these houses.
Hint 5
The problem is now reduced to a Minimum Spanning Tree problem.
Preparing judge…