05 August 2008
一个村子有 n 栋房子。我们想通过打井和铺设管道来为所有房屋供水。
对于每栋房屋 i，我们可以直接在其内部用成本 wells[i - 1] 建造一口井（注意由于 0 索引而导致的 -1），或者将水从另一口井引入它。在房屋之间铺设管道的成本由管道阵列给出，其中每个管道[j] = [house1j, house2j, costj] 表示使用管道将 house1j 和 house2j 连接在一起的成本。连接是双向的，相同的两栋房子之间可能有多个有效连接，但成本不同。
返回向所有房屋供水的最低总成本。
Prim’s算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
//No base case by looking at constraints.
Set<Integer> visited = new HashSet<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((int[] a, int[] b) -> a[2] - b[2]);
List<Integer[]>[] adList = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adList[i] = new ArrayList();
}
for (int[] pipe : pipes) {
int h1 = pipe[0];
int h2 = pipe[1];
int c = pipe[2];
adList[h1].add(new Integer[]{h2, c});
adList[h2].add(new Integer[]{h1, c});
}
//add vertex 0 with edges to all other vertex with initial weights from well.
for (int i = 1; i <= n; i++) {
pq.offer(new int[]{0, i, wells[i - 1]});
}
visited.add(0);
int count = 1; //I need total n edges (including one connecting virtual vertex.)
int minCost = 0;
while (!pq.isEmpty() && count <= n) {
int[] top = pq.poll();
if (visited.contains(top[1])) continue;
visited.add(top[1]);
minCost += top[2];
int dest = top[1];
count++;//Now add edges in PQ. where either source or destination is this vertex
//and exclude visited nodes.
for (Integer[] array : adList[dest]) {
if (!visited.contains(array[0])) {
pq.offer(new int[]{dest, array[0], array[1]});
}
}
}
return minCost;
}
}