上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
}
};
golang 解法, 执行用时: 84 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-22 09:02:42
func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
// 不能用 kruskal，因为至少要有一个 house 是用 well 的
// 所以不能一开始就将所有 pipe 加入优先队列
// 将邻接矩阵变为邻接链表
graph := make([][][]int, n)
for i := 0; i < n; i++ {
graph[i] = make([][]int, 0)
}
for _, pipe := range pipes {
// 将所有 house idx 减 1
from, to, cost := pipe[0] - 1, pipe[1] - 1, pipe[2]
graph[from] = append(graph[from], []int{to, cost})
graph[to] = append(graph[to], []int{from, cost})
}
// 初始化 pq，只包括井
pq := Heap(make([][]int, 0))
for house, cost := range wells {
heap.Push(&pq, []int{house, cost})
}
visited := make([]bool, n)
numVisited := 0
totalCost := 0
for numVisited < n {
edge := heap.Pop(&pq).([]int)
house, cost := edge[0], edge[1]
// 因为刚开始所有的井都被加入了
// 而且通往一个 house 的边可能被重复加入
// 所以 pop 出来的 house 仍有可能重复
if visited[house] {
continue
}
visited[house] = true
numVisited++
totalCost += cost
for _, edge := range graph[house] {
if visited[edge[0]] {
continue
}
heap.Push(&pq, edge)
}
}
return totalCost
}
// 优先队列的每个元素是 长度为 2 的[]int
// 0 元素是尚未通水的 house number，1 元素是 cost
type Heap [][]int
func (h Heap) Len() int {return len(h)}
func (h Heap) Less(i, j int) bool {return h[i][1] < h[j][1]} // compare cost
func (h Heap) Swap(i, j int) {h[i], h[j] = h[j], h[i]}
func (h *Heap) Push(x interface{}) {
*h = append(*h, x.([]int))
}
func (h *Heap) Pop() interface{} {
old := *h
ret := old[len(old) - 1]
*h = old[:len(old) - 1]
return ret
}
golang 解法, 执行用时: 56 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-22 09:02:32
import "sort"
type UnionFind struct {
Parent []int
Cost []int
}
func (self *UnionFind) Init(n int, wells []int) {
self.Parent = make([]int, n)
self.Cost = make([]int, n)
for i := 0; i < n; i++ {
self.Parent[i] = i
self.Cost[i] = wells[i]
}
}
func (self *UnionFind) Find(i int) int {
if self.Parent[i] == i {
return i
}
tparent := self.Find(self.Parent[i])
self.Parent[i] = tparent
self.Cost[i] = self.Cost[tparent]
return tparent
}
func (self *UnionFind) Union(i, j, c int) int {
p1 := self.Find(i)
p2 := self.Find(j)
if p1 == p2 {
return 0
}
if self.Cost[p1] <= self.Cost[p2] && self.Cost[p2] >= c {
// keep i well
save := self.Cost[p2] - c
self.Parent[p2] = p1
self.Cost[p2] = self.Cost[p1]
return save
} else if self.Cost[p1] >= self.Cost[p2] && self.Cost[p1] >= c {
// keep j well
save := self.Cost[p1] - c
self.Parent[p1] = p2
self.Cost[p1] = self.Cost[p2]
return save
}
return 0
}
type Pipes [][]int
func (self Pipes) Len() int { return len(self) }
func (self Pipes) Swap(i, j int) { self[i], self[j] = self[j], self[i] }
func (self Pipes) Less(i, j int) bool { return self[i][2] < self[j][2] }
func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
cost := 0
for _, c := range wells {
cost += c
}
uf := UnionFind{}
uf.Init(n, wells)
p := Pipes{}
for i := 0; i < len(pipes); i++ {
p = append(p, pipes[i])
}
sort.Sort(p)
pipes = p
for _, pair := range pipes {
house1 := pair[0]-1
house2 := pair[1]-1
c := pair[2]
link := uf.Union(house1, house2, c)
if link == 0 {
continue
}
cost -= link
}
return cost
}
cpp 解法, 执行用时: 100 ms, 内存消耗: 33.5 MB, 提交时间: 2023-10-22 09:01:38
class UnionFindMinTree2 {
public:
vector<pair<int, int>> nodes;
UnionFindMinTree2(int n, vector<int>& wells) {
nodes = vector<pair<int, int>>(n);
for (int i = 0; i < n; ++i)
nodes[i] = { i, wells[i] };
}
pair<int, int> find(int& x) {
if (nodes[x].first == x)
return nodes[x];
return nodes[x] = find(nodes[x].first);
}
void unionEle(int& a, int& b) {
pair<int, int> pa = find(a);
pair<int, int> pb = find(b);
if (pa.first != pb.first)
nodes[pb.first] = pa;
}
};
class Solution {
public:
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
sort(pipes.begin(), pipes.end(), [](vector<int>& a, vector<int>& b) { return a[2] < b[2]; });
UnionFindMinTree2 ufmt(n, wells);
int result = 0;
for (int i : wells)
result += i;
for (int i = 0; i < pipes.size(); ++i) {
int x1 = pipes[i][0] - 1;
int x2 = pipes[i][1] - 1;
int cost = pipes[i][2];
pair<int, int> p1 = ufmt.find(x1);
pair<int, int> p2 = ufmt.find(x2);
if (p1 != p2) {
if (p1.second <= p2.second && p2.second >= cost) {
result = result - p2.second + cost;
ufmt.unionEle(x1, x2);
}
else if (p1.second >= cost) {
result = result - p1.second + cost;
ufmt.unionEle(x2, x1);
}
}
}
return result;
}
};
python3 解法, 执行用时: 144 ms, 内存消耗: 23.4 MB, 提交时间: 2023-10-22 08:58:37
class Solution:
def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
# 邻接表表示的双向图
graph = defaultdict(list)
# 添加索引为0的虚拟顶点。
# 然后在每一栋房子上加一条边，按成本加权
for index, cost in enumerate(wells):
graph[0].append((cost, index + 1))
# 将双向边添加到图中
for house_1, house_2, cost in pipes:
graph[house_1].append((cost, house_2))
graph[house_2].append((cost, house_1))
# 用于维护已添加到的所有顶点的集合
# 最终的 MST(最小生成树)从顶点 0 开始。
mst_set = set([0])
# 堆维护要访问的边的顺序，
# 从起源于顶点0的边开始。
# 注意：我们能够从任意节点开始。
heapq.heapify(graph[0])
edges_heap = graph[0]
total_cost = 0
while len(mst_set) < n + 1:
cost, next_house = heapq.heappop(edges_heap)
if next_house not in mst_set:
# 将新顶点添加到集合中
mst_set.add(next_house)
total_cost += cost
# 在下一轮扩大候选边的选择范围
for new_cost, neighbor_house in graph[next_house]:
if neighbor_house not in mst_set:
heapq.heappush(edges_heap, (new_cost, neighbor_house))
return total_cost
java 解法, 执行用时: 42 ms, 内存消耗: 46.8 MB, 提交时间: 2023-10-22 08:57:44
class Solution {
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
// 最小堆，以维护要访问的边的顺序。
PriorityQueue<Pair<Integer, Integer>> edgesHeap =
new PriorityQueue<>(n, (a, b) -> (a.getKey() - b.getKey()));
// 图在邻接表中的表示
List<List<Pair<Integer, Integer>>> graph = new ArrayList<>(n + 1);
for (int i = 0; i < n + 1; ++i) {
graph.add(new ArrayList<Pair<Integer, Integer>>());
}
// 添加索引为0的虚拟顶点，
// 然后在每一栋房子上加一条边，按成本加权
for (int i = 0; i < wells.length; ++i) {
Pair<Integer, Integer> virtualEdge = new Pair<>(wells[i], i + 1);
graph.get(0).add(virtualEdge);
// 使用来自虚拟顶点的边初始化堆。
edgesHeap.add(virtualEdge);
}
// 将双向边添加到图中
for (int i = 0; i < pipes.length; ++i) {
int house1 = pipes[i][0];
int house2 = pipes[i][1];
int cost = pipes[i][2];
graph.get(house1).add(new Pair<Integer, Integer>(cost, house2));
graph.get(house2).add(new Pair<Integer, Integer>(cost, house1));
}
// 从虚拟顶点0开始探索
Set<Integer> mstSet = new HashSet<>();
mstSet.add(0);
int totalCost = 0;
while (mstSet.size() < n + 1) {
Pair<Integer, Integer> edge = edgesHeap.poll();
int cost = edge.getKey();
int nextHouse = edge.getValue();
if (mstSet.contains(nextHouse)) {
continue;
}
// 将新顶点添加到集合中
mstSet.add(nextHouse);
totalCost += cost;
// 扩大下一轮优势候选人的选择范围
for (Pair<Integer, Integer> neighborEdge : graph.get(nextHouse)) {
if (!mstSet.contains(neighborEdge.getValue())) {
edgesHeap.add(neighborEdge);
}
}
}
return totalCost;
}
}
class Solution2 {
private void dfs(List<Integer>[] adjList, int[] visited, int startNode) {
visited[startNode] = 1;
for (int i = 0; i < adjList[startNode].size(); i++) {
if (visited[adjList[startNode].get(i)] == 0) {
dfs(adjList, visited, adjList[startNode].get(i));
}
}
}
public int countComponents(int n, int[][] edges) {
int components = 0;
int[] visited = new int[n];
List<Integer>[] adjList = new ArrayList[n];
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<Integer>();
}
for (int i = 0; i < edges.length; i++) {
adjList[edges[i][0]].add(edges[i][1]);
adjList[edges[i][1]].add(edges[i][0]);
}
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
components++;
dfs(adjList, visited, i);
}
}
return components;
}
}
