LeetCode 1168 Optimization of water allocation

There are n families in the village, and we can dig wells or build water pipes to supply water to each family.

For each household, we can dig wells directly in their homes by spending wells[i] or connect them to other wells through water pipes. The cost of laying water pipes between every two households is represented by an array of pipes. pipes[i] = [house1, house2, cost] indicates that the cost of laying water pipes between households 1 and 2 is cost.

Request a minimum cost of water for all residents.

Example 1: Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]].

Output: 3 Explanations:

the image shows the costs of connecting houses using pipes.

the best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

Hint:

1 <= n <= 10000

wells.length == n
0 <= wells[i] <= 10^5
1 <= pipes.length <= 10000
1 <= pipes[i][0], pipes[i][1] <= n
0 <= pipes[i][2] <= 10^5
pipes[i][0] != pipes[i][1]

Question, it costs a certain amount of money to dig wells in each city, and it is also possible to use well water from other cities, and it costs a certain amount of money to build connecting pipes between cities, so how to arrange the irrigation of all cities that can cost the least money.

This is the shortest path that connects all the points Minimum spanning tree problem, which looks at the city as the point in the diagram and the pipe connecting the city as the edge connecting the two points. The cost of drilling a well here is directly at the point, and not all points are connected by edges, so for convenience, we can assume a point（root）0, where the cost of self points can be compared toconnection, the cost can be0-ibetween the costs. This allows us to construct a connected graph with all the points and edges. The problem of finding the shortest path and the smallest spanning tree in a connectivity graph.

Refer to the Wikipedia for several solutions to this type of problem in the extended reading.

Step: Createpojo edgecost(node1, node2, cost) - the cost of connecting edges between node 1 and node 2。Imagine onerootDotto build a graph that connects all nodes and[0,i] -i is the node [1,n].It's a nodewith, the value of the edge is the nodeiThe cost of drilling a wellwells[i];Convert the cost of drilling wells and city connection points into nodes and edges of the graph. Sort the values of the edges of the graph (from smallest to largest) and traverse the edges of the graph to determine whether the two nodes are connected (union-findIf all nodes are connected, the minimum path obtained is the minimum cost, and it is returned for each timeunion, number of nodesn-1, ifn==0Indicates that all nodes are connected and can exit early without continuing to access the remaining edges.

Here, a weighted union-find is used to determine whether the two nodes are connected, and whether the nodes are connected.

As you can see from the diagram, all the nodes are connected at the end.

Complexity analysis

Time Complexity:o(eloge) -e is the number of edges of the graphSpace Complexity:o(e)

There is a maximum of one figuren(n-1) 2 - n is the number of nodes in the graphStrip edges (fully connected graphs).

class optimizewaterdistribution for (int p : pipes) collections.sort(costs); int mincosts = 0; unionfind uf = new unionfind(n); for (edgecost edge : costs) return mincosts; }class edgecost implements comparable @override public int compareto(edgecost o) class unionfind rank = new int[n + 1]; public int find(int x) public void union(int x, int y) else }

class solution: def mincosttosupplywater(self, n: int, wells: list[int], pipes: list[list[int]])int: union_find = def find(x): return x if x == union_find[x] else find(union_find[x]) def union(x, y): px = find(x) py = find(y) union_find[px] = py graph_wells = [[cost, 0, i] for i, cost in enumerate(wells, 1)] graph_pipes = [[cost, i, j] for i, j, cost in pipes] min_costs = 0 for cost, x, y in sorted(graph_wells + graph_pipes): if find(x) == find(y): continue union(x, y) min_costs += cost n -= 1 if n == 0: return min_costs