Cheapest Water Supply

MediumAdvanced Graphs

Problem

A village has n farms. Farm i can dig its own well for wells[i]. Farms can also share water through pipes: pipes[j] = [u, v, cost] lays a two-way pipe between farms u and v.

Return the minimum total cost so that every farm has water, either from its own well or through pipes from a farm that has one.

Example 1

Input:
wells = [3,4,2], pipes = [[0,1,1],[1,2,1]]
Output:
4

Dig a well at farm 2 (2) and lay both pipes (1 + 1).

Example 2

Input:
wells = [1,1], pipes = [[0,1,5]]
Output:
2

Two wells are cheaper than one well plus the pipe.

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ pipes.length ≤ 10^4
  • 1 ≤ wells[i], cost ≤ 10^5
  • Parallel pipes may exist.

Hint

Show the first hint

Pipes alone form a spanning-tree problem, but wells are a different kind of cost. Can you turn a well into an edge?

Walkthrough

How to approach it

01Clarify before coding

  • Can several farms dig wells? Yes, any number.
  • Are pipes two-way? Yes.
  • Is at least one well needed? Yes, pipes alone carry no water.

02Brute force

Try every subset of farms that dig wells, and for each connect the rest with the cheapest pipes (an MST per component).

Cost: 2^n subsets: infeasible.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.