Study Notes
  • Kuma Blog
  • AI
    • AI-Resources
    • AI-books
    • AI_Blogs
      • Exploring the Future of AI in 2025: Key Trends and Predictions
      • Exploring the Power of Kuma AI Tools in 2025
      • The Future of AI in 2025: Predicting the Next Big Trends
      • The Future of AI in 2025: Predictions and Insights
      • The Future of AI in 2025: Trends and Predictions
      • The-Future-of-AI-in-2025-Trends-to-Watch_2025-05-30
      • Untitled-1748347240822_2025-05-27
      • Untitled-1748520038559_2025-05-29
    • Kuma_AI_Daily_NewsLetter
      • Kuma AI Daily News Letter 2025-05-25
      • Kuma AI Daily News Letter 2025-05-26
      • Kuma AI Daily News Letter 2025-05-27
      • Kuma AI Daily News Letter 2025-05-28
      • Kuma AI Daily News Letter 2025-05-29
      • Kuma AI Daily News Letter 2025-05-30
      • Kuma AI Daily News Letter 2025-05-31
    • Prompts
      • Prompts Free Courses
    • AI_Agents
      • Kuma AI Travel Agent
        • Kuma AI Travel Agent
  • Movies
    • 2024
    • 2024
    • 2024
  • Google
    • chunked-palindrome
  • Setup
    • How to add a new user into Ubuntu and setup ssh key?
    • How to set up VSCode remote server connect with browser with Docker
  • kubernetes
  • Books
    • Designing-Data-Intensive-Applications
      • 第一章 — 可靠性,可扩展性,可维护性的应用程序(Reliable, Scalable, and Maintainable Applications)
    • System-Performance
      • Design-Data-Intensive-Application
      • Chapter 2: Methodologies
  • Languages
    • japanese
      • japanese-week
  • Leetcode
    • 30DayChallenge
      • LRU-cache
      • backspace-string-compare
      • binary-tree-maximum-path-sum
      • bitwise-and-number-range
      • check-string-valid-sequence-from-root-to-leaves-path-in-bst
      • construct-binary-search-tree-from-preorder-traversal
      • contiguous-array
      • counting-elements
      • diameter-of-binary-tree
      • first-unique-number
      • group-anagrams
      • jump-game
      • last-stone-weight
      • leftmost-column-with-at-least-a-one
      • longest-common-subsequect
      • maximal-square
      • maximum-subarray
      • middle-of-the-linked-list
      • min-stack
      • minimun-path-sum
      • move-zeroes
      • perform-string-shifts
      • product-of-array-except-itself
      • search-in-rotated-sorted-array
      • subarray-sum-equals-k
      • valid-parenthesis-string
    • English Solution
      • 1168.optimize-water-distribution-in-a-village-en
      • 1171.remove-zero-sum-consecutive-nodes-from-linked-list-en
      • 1177.can-make-palindrome-from-substring-en
      • 1343.number-of-avg-subarr-sizek-greater-or-equal-threshold
      • 1345.jump-game-iv
      • 25.reverse-nodes-in-k-groups-en
      • 474.ones-and-zeros-en
      • 53.maximum-sum-subarray-en
      • 547.friend-circles-en
      • 79.word-search-en
    • May2020Challenge
      • check-if-straight-line
      • cousins-in-binary-tree
      • find-town-judge
      • first-bad-version
      • first-unique-character-in-a-string
      • flood-fill
      • implement-trie
      • jewels-and-stones
      • majority-element
      • maximum-sum-circular-subarray
      • number-complement
      • odd-even-linkedlist
      • ransom-note
      • remove-k-digits
      • single-element-in-sorted-array
      • valid-perfect-square
    • python
      • 000017-Letter-Combinations-of-a-Phone-Number
      • 000032-Longest-Valid-Parentheses
      • 000033-Search-in-Rotated-Sorted-Array
      • 000046-Permutations
      • 000074-Search-a-2D-Matrix
      • 000077-Combinations
      • 000081-Search-in-Rotated-Sorted-Array-II
      • 000137-single-number-ii
      • 000139-Word-Break
      • 000207-courses-schedule
      • 000209-Minimum-Size-Subarray-Sum
      • 000376-wiggle-subsequence
      • 000445-Add-Two-Numbers-II
      • 000486-Predict-the-Winner
      • 000518-Coin-Change-II
      • 000673-Number-of-Longest-Increasing-Subsequence
      • 000688-Knight-Probability-in-Chessboard
      • 000735-Asteroid-Collision
      • 000852-Peak-Index-in-a-Mountain-Array
      • 859-Buddy-Strings
      • 000864-Shortest-Path-to-Get-All-Keys
      • 000920-Number-of-Music-Playlists
      • 001218-Longest-Arithmetic-Subsequence-of-Given-Difference
      • 001235-Maximum-Profit-in-Job-Scheduling
      • 001493-Longest-Subarray-of 1-After-Deleting-One-Element
      • Problem
      • 002024-Maximize-the-Confusion-of-an-Exam
      • 2305-Fair-Distribution-of-Cookies
      • 002616-Minimize-the-Maximum-Difference-of-Pairs
      • 00802-Find-Eventual-Safe-States
    • 中文版解题
      • 1147.longest-chunked-palindrome-decomposition-cn
      • 1168.optimize-water-distribution-in-a-village-cn
      • 1171.remove-zero-sum-consecutive-nodes-from-linked-list-cn
      • 1177.can-make-palindrome-from-substring-cn
      • 215.kth-largest-element-in-an-array-cn
      • 25.reverse-nodes-in-k-groups-cn
      • 30.substring-with-concatenation-of-all-words-cn
      • 4.median-of-two-sorted-array-cn
      • 460.LFU-cache-cn
      • 474.ones-and-zeros-cn
      • 53.maximum-sum-subarray-cn
      • 79.word-search-cn
  • Readings
    • 2020
      • Design-Data-Intensive-Application
      • 亲爱的提奥
      • 理想国
      • 贫穷的本质
Powered by GitBook
On this page
  • 题目地址
  • 题目描述
  • 思路
  • 复杂度分析
  • 关键点分析
  • 代码 (Java/Python3)
  • 延伸阅读

Was this helpful?

  1. Leetcode
  2. 中文版解题

1168.optimize-water-distribution-in-a-village-cn

Previous1147.longest-chunked-palindrome-decomposition-cnNext1171.remove-zero-sum-consecutive-nodes-from-linked-list-cn

Last updated 5 years ago

Was this helpful?

题目地址

题目描述

There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.

For each house i, we can either build a well inside it directly with cost wells[i], or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes, where each pipes[i] = [house1, house2, cost] represents the cost to connect house1 and house2 together using a pipe. Connections are bidirectional.

Find the minimum total cost to supply water to all houses.

Example 1:

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: 
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.

Constraints:

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]

example 1 pic:

思路

题意,在每个城市打井需要一定的花费,也可以用其他城市的井水,城市之间建立连接管道需要一定的花费,怎么样安排可以花费最少的前灌溉所有城市。

这是一道连通所有点的最短路径/最小生成树问题,把城市看成图中的点,管道连接城市看成是连接两个点之间的边。这里打井的花费是直接在点上,而且并不是所有 点之间都有边连接,为了方便,我们可以假想一个点(root)0,这里自身点的花费可以与 0 连接,花费可以是 0-i 之间的花费。这样我们就可以构建一个连通图包含所有的点和边。 那在一个连通图中求最短路径/最小生成树的问题.

参考延伸阅读中,维基百科针对这类题给出的几种解法。

解题步骤:

  1. 创建 POJO EdgeCost(node1, node2, cost) - 节点1 和 节点2 连接边的花费。

  2. 假想一个root 点 0,构建图

  3. 连通所有节点和 0,[0,i] - i 是节点 [1,n],0-1 是节点 0 和 1 的边,边的值是节点 i 上打井的花费 wells[i];

  4. 把打井花费和城市连接点转换成图的节点和边。

  5. 对图的边的值排序(从小到大)

  6. 遍历图的边,判断两个节点有没有连通 (Union-Find),

    • 已连通就跳过,继续访问下一条边

    • 没有连通,记录花费,连通节点

  7. 若所有节点已连通,求得的最小路径即为最小花费,返回

  8. (对#7 的优化) 对于每次union, 节点数 n-1, 如果 n==0 说明所有节点都已连通,可以提前退出,不需要继续访问剩余的边。

这里用加权Union-Find 判断两个节点是否连通,和连通未连通的节点。

举例:n = 5, wells=[1,2,2,3,2], pipes=[[1,2,1],[2,3,1],[4,5,7]]

如图:

从图中可以看到,最后所有的节点都是连通的。

复杂度分析

  • 时间复杂度: O(ElogE) - E 是图的边的个数

  • 空间复杂度: O(E)

一个图最多有 n(n-1)/2 - n 是图中节点个数 条边 (完全连通图)

关键点分析

  1. 构建图,得出所有边

  2. 对所有边排序

  3. 遍历所有的边(从小到大)

  4. 对于每条边,检查是否已经连通,若没有连通,加上边上的值,连通两个节点。若已连通,跳过。

代码 (Java/Python3)

Java code

  class OptimizeWaterDistribution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
      List<EdgeCost> costs = new ArrayList<>();
      for (int i = 1; i <= n; i++) {
        costs.add(new EdgeCost(0, i, wells[i - 1]));
      }
      for (int[] p : pipes) {
        costs.add(new EdgeCost(p[0], p[1], p[2]));
      }
      Collections.sort(costs);
      int minCosts = 0;
      UnionFind uf = new UnionFind(n);
      for (EdgeCost edge : costs) {
        int rootX = uf.find(edge.node1);
        int rootY = uf.find(edge.node2);
        if (rootX == rootY) continue;
        minCosts += edge.cost;
        uf.union(edge.node1, edge.node2);
        // for each union, we connnect one node
        n--;
        // if all nodes already connected, terminate early
        if (n == 0) {
          return minCosts;
        }
      }
      return minCosts;
    }

    class EdgeCost implements Comparable<EdgeCost> {
      int node1;
      int node2;
      int cost;
      public EdgeCost(int node1, int node2, int cost) {
        this.node1 = node1;
        this.node2 = node2;
        this.cost = cost;
      }

      @Override
      public int compareTo(EdgeCost o) {
        return this.cost - o.cost;
      }
    }

    class UnionFind {
      int[] parent;
      int[] rank;
      public UnionFind(int n) {
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) {
          parent[i] = i;
        }
        rank = new int[n + 1];
      }
      public int find(int x) {
        return x == parent[x] ? x : find(parent[x]);
      }
      public void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py) return;
        if (rank[px] >= rank[py]) {
          parent[py] = px;
          rank[px] += rank[py];
        } else {
          parent[px] = py;
          rank[py] += rank[px];
        }
      }
    }
  }

Pythong3 code

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        union_find = {i: i for i in range(n + 1)}

        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

延伸阅读

https://leetcode.com/problems/optimize-water-distribution-in-a-village/
最短路径问题
Dijkstra算法
Floyd-Warshall算法
Bellman-Ford算法
Kruskal算法
Prim's 算法
example 1
minimum cost