043.最小生成树

前置知识：讲解 025、027 - 堆的内容、讲解 056、057 - 并查集的内容、图

最小生成树 §

在无向带权图中选择择一些边，在保证联通性的情况下，边的总权值最小

最小生成树可能不只一棵，只要保证边的总权值最小，就都是正确的最小生成树

如果无向带权图有 n 个点，那么最小生成树一定有 n-1 条边（不能形成环，否则就不是最小了）

扩展：最小瓶颈树 §

最小瓶颈树：将所有点联通，保证最大边（权重）尽量小

最小生成树一定是最小瓶颈树（题目4）；最小瓶颈树不一定是最小生成树

证明略

Kruskal 算法 §

克鲁斯卡尔算法，最常用

甚至不需要建图，只需要把点加到并查集即可

思路 §

1. 把所有的边，根据权值从小到大排序，从权值小的边开始考虑
2. 如果连接当前的边不会形成环，就选择当前的边
3. 如果连接当前的边会形成环，就不要当前的边
4. 考察完所有边之后（够 n-1 条边），最小生成树的也就得到了

正确性证明略！是贪心的思路

复杂度 §

• 时间复杂度：$O(m\ast lo{g}^m)+O(n)+O(m)$
  • $O(m\ast lo{g}^m)$：将边按权重排序
  • $O(n)$：并查集，初始所有点自己是一个集合
  • $O(m)$：每条边在并查集看是否形成环
• 空间复杂度：$O(n)$，点的并查集

Prim 算法 §

普里姆算法，不算常用

需要建图

思路 §

1. 解锁的点的集合叫 set（普通集合）、解锁的边的集合叫 heap（小根堆）。set 和 heap 都为空
2. 可从任意点开始，开始点加入到 set，开始点的所有边加入到 heap
3. 从 heap 中弹出权值最小的边 e，查看边 e 所去往的点 x
   • 如果 x 已经在 set 中，边 e 舍弃，重复步骤 3
   • 如果 x 不在 set 中，边 e 属于最小生成树，把 x 加入 set，重复步骤 3
4. 当 heap 为空，最小生成树的也就得到了

正确性证明略！是贪心的思路

复杂度 §

• 时间复杂度：$O(n+m)+O(m\ast lo{g}^m)$
  • $O(n+m)$：建图
  • $O(m\ast lo{g}^m)$：边从小根堆加入、弹出，堆操作是 $lo{g}^m$（堆中存边）
• 空间复杂度：$O(n+m)$，set（点） + heap（边）

Prim 算法的优化 §

比较难，不感兴趣可以跳过，请一定要对堆很熟悉！

思路 §

1. 小根堆里放 (节点, 到达节点的花费)，根据到达节点的花费来组织小根堆
2. 小根堆弹出 (u 节点, 到达 u 节点的花费 y)，y 累加到总权重上去，然后考察 u 出发的每一条边
   • 假设，u 出发的边，去往 v 节点，权重 w
   • 如果 v 已经弹出过了（发现过），忽略该边
   • 如果 v 从来没有进入过堆，向堆里加入记录 (v, w)
   • 如果 v 在堆里，且记录为 (v, x)
     • 如果 w < x，则记录更新成 (v, w)，然后调整该记录在堆中的位置（维持小根堆）
     • 如果 w >= x，忽略该边
3. 重复步骤 2，直到小根堆为空

复杂度 §

• 时间复杂度：$O(n+m)+O((m+n)\ast lo{g}^n)$
  • $O(n+m)$：建图
  • $O((m+n)\ast lo{g}^n)$：边中每个点从小根堆加入、弹出，堆操作是 $lo{g}^n$（堆中存点）
• 空间复杂度：$O(n)$，where（点） + heap（点）

总结 §

• Kruskal 算法和普通 Prim 算法时间复杂度一样，是 $lo{g}^m$
  • Kruskal 更好写
• 优化 Prim 算法时间复杂度不同，是 $lo{g}^n$
  • 当边的数据量大，点的数据量少，使用优化 Prim 算法更优

大多数情况使用 Kruskal，如下面的题目都用 Kruskal

备注 §

最小生成树扩展很多，除了这节课讲的，大部分都是比赛需要的内容，有兴趣可以继续研究

题目1.最小生成树模版 §

测试链接 §

P3366【模板】最小生成树

Kruskal 算法 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)
 
const (
	MAXN = 5001
	MAXM = 2e5 + 1
)
 
var (
	n      int
	m      int
	father = [MAXN]int{}
	// [from, to, weight]
	edges = [MAXM][3]int{}
)
 
func build() {
	for i := 1; i <= n; i++ {
		father[i] = i
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
// 本来就是一个集合：false
// 不是一个集合，合并：true
func union(a, b int) bool {
	af := find(a)
	bf := find(b)
	if af == bf {
		return false
	}
	father[af] = bf
	return true
}
 
func main() {
	// s := `4 5
	// 1 2 2
	// 1 3 2
	// 1 4 3
	// 2 3 4
	// 3 4 3`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		for i := 0; i < m; i++ {
			in.Scan()
			edges[i][0], _ = strconv.Atoi(in.Text())
			in.Scan()
			edges[i][1], _ = strconv.Atoi(in.Text())
			in.Scan()
			edges[i][2], _ = strconv.Atoi(in.Text())
		}
		// 按权重排序
		sort.Slice(edges[:m], func(i, j int) bool {
			return edges[i][2] < edges[j][2]
		})
		ans := 0
		edgeCnt := 0
		for i := 0; i < m; i++ {
			if union(edges[i][0], edges[i][1]) {
				ans += edges[i][2]
				edgeCnt++
			}
		}
		if edgeCnt == n-1 {
			fmt.Fprintln(out, ans)
		} else {
			// 该图不连通
			fmt.Fprintln(out, "orz")
		}
	}
	out.Flush()
}

Prim 算法 §

package main
 
import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 5001
	MAXM = 4e5 + 1 // 注意无向图，边数要 *2
)
 
var (
	n int
	m int
 
	head   = [MAXN]int{}
	next   = [MAXM]int{}
	to     = [MAXM]int{}
	weight = [MAXM]int{}
	cnt    = 1
 
	exist    = [MAXN]bool{}
	minHeap  = MinHeap{}
	heapSize int
)
 
func build() {
	cnt = 1
	heapSize = 0
	for i := 1; i <= n; i++ {
		head[i] = 0
		exist[i] = false
	}
}
 
func addEdge(f, t, w int) {
	next[cnt] = head[f]
	to[cnt] = t
	weight[cnt] = w
	head[f] = cnt
	cnt++
}
 
// [to, weight]
type MinHeap [MAXM][2]int
 
func (*MinHeap) Len() int {
	return heapSize
}
 
func (h *MinHeap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}
 
func (h *MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	val := v.([2]int)
	h[heapSize][0] = val[0]
	h[heapSize][1] = val[1]
	heapSize++
}
 
func (h *MinHeap) Pop() any {
	heapSize--
	return h[heapSize]
}
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		f, t, w := 0, 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			f, _ = strconv.Atoi(in.Text())
			in.Scan()
			t, _ = strconv.Atoi(in.Text())
			in.Scan()
			w, _ = strconv.Atoi(in.Text())
			addEdge(f, t, w)
			addEdge(t, f, w)
		}
		exist[1] = true
		for i := head[1]; i > 0; i = next[i] {
			heap.Push(&minHeap, [2]int{to[i], weight[i]})
		}
		nodeCnt := 1
		ans := 0
		for heapSize > 0 {
			cur := heap.Pop(&minHeap).([2]int)
			if !exist[cur[0]] {
				exist[cur[0]] = true
				nodeCnt++
				ans += cur[1]
				for i := head[cur[0]]; i > 0; i = next[i] {
					heap.Push(&minHeap, [2]int{to[i], weight[i]})
				}
			}
		}
 
		if nodeCnt == n {
			fmt.Fprintln(out, ans)
		} else {
			fmt.Fprintln(out, "orz")
		}
	}
	out.Flush()
}

优化的 Prim 算法 §

package main
 
import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 5001
	MAXM = 4e5 + 1 // 注意无向图，边数要 *2
)
 
var (
	n int
	m int
 
	head   = [MAXN]int{}
	next   = [MAXM]int{}
	to     = [MAXM]int{}
	weight = [MAXM]int{}
	cnt    = 1
 
	// -1: 从来没有进入过堆
	// -2: 已经弹出过了（发现过）
	// >=0: 在堆的哪个位置
	where    = [MAXN]int{}
	minHeap  = MinHeap{}
	heapSize int
)
 
func build() {
	cnt = 1
	heapSize = 0
	for i := 1; i <= n; i++ {
		head[i] = 0
		where[i] = -1
	}
}
 
func addEdge(f, t, w int) {
	next[cnt] = head[f]
	to[cnt] = t
	weight[cnt] = w
	head[f] = cnt
	cnt++
}
 
func addOrUpdateOrIgnore(i int) {
	t := to[i]
	w := weight[i]
	if where[t] == -2 {
		// 已经弹出过了（发现过）
		// 什么都不做
	} else if where[t] == -1 {
		// 从来没有进入过堆
		heap.Push(&minHeap, [2]int{t, w})
	} else {
		// 在堆的 where[t] 位置
		if w < minHeap[where[t]][1] {
			minHeap[where[t]][1] = w
			heap.Fix(&minHeap, where[t])
		}
	}
}
 
// [to, weight]
type MinHeap [MAXN][2]int
 
func (*MinHeap) Len() int {
	return heapSize
}
 
func (h *MinHeap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}
 
func (h *MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	// 注意这里：where 也要正确更新
	where[h[i][0]] = i
	where[h[j][0]] = j
}
 
func (h *MinHeap) Push(v any) {
	val := v.([2]int)
	h[heapSize][0] = val[0]
	h[heapSize][1] = val[1]
	// 注意这里：where 也要正确更新
	where[val[0]] = heapSize
	heapSize++
}
 
func (h *MinHeap) Pop() any {
	heapSize--
	res := h[heapSize]
	// 注意这里：where 也要正确更新
	where[res[0]] = -2
	return res
}
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		f, t, w := 0, 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			f, _ = strconv.Atoi(in.Text())
			in.Scan()
			t, _ = strconv.Atoi(in.Text())
			in.Scan()
			w, _ = strconv.Atoi(in.Text())
			addEdge(f, t, w)
			addEdge(t, f, w)
		}
		where[1] = -2
		for i := head[1]; i > 0; i = next[i] {
			addOrUpdateOrIgnore(i)
		}
		nodeCnt := 1
		ans := 0
		for heapSize > 0 {
			cur := heap.Pop(&minHeap).([2]int)
			nodeCnt++
			ans += cur[1]
			for i := head[cur[0]]; i > 0; i = next[i] {
				addOrUpdateOrIgnore(i)
			}
		}
 
		if nodeCnt == n {
			fmt.Fprintln(out, ans)
		} else {
			fmt.Fprintln(out, "orz")
		}
	}
	out.Flush()
}

对比 §

题目2.水资源分配优化 §

题目描述 §

村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。

对于每个房子 i，我们有两种可选的供水方案：

1. 一种是直接在房子内建造水井，成本为 wells[i-1]（注意 -1，因为索引从 0 开始 ）
2. 另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1j, house2j, costj]：代表用管道将 house1j 和 house2j 连接在一起的成本。连接是双向的。

请返回为所有房子都供水的最低总成本

测试链接 §

1168.水资源分配优化

思路 §

两种情况，要分开讨论？

不用那么麻烦，在房子内建造水井相当于用管道将水井和房子连接在一起，这样就转化为一种情况了

加一个点：水井，编号为 0，将所有点联通的最小代价——最小生成树

答案 §

package main
 
import (
	"fmt"
	"sort"
)
 
var (
	father []int
)
 
func minCostToSupplyWater(n int, wells []int, pipes [][3]int) int {
	build(n)
	edges := make([][3]int, 0, len(wells)+len(pipes))
	for i, well := range wells {
		// 0: 水井
		edges = append(edges, [3]int{0, i + 1, well})
	}
	edges = append(edges, pipes...)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i][2] < edges[j][2]
	})
 
	ans := 0
	for _, edge := range edges {
		if union(edge[0], edge[1]) {
			ans += edge[2]
		}
	}
	return ans
}
 
func build(n int) {
	father = make([]int, n+1)
	for i := range father {
		father[i] = i
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) bool {
	af := find(a)
	bf := find(b)
	if af == bf {
		return false
	}
	father[af] = bf
	return true
}
 
type Test struct {
	n     int
	wells []int
	pipes [][3]int
	ans   int
}
 
func main() {
	tests := []Test{
		{3, []int{1, 2, 2}, [][3]int{{1, 2, 1}, {2, 3, 1}}, 3},
		{2, []int{1, 1}, [][3]int{{1, 2, 1}}, 2},
	}
	for _, t := range tests {
		if minCostToSupplyWater(t.n, t.wells, t.pipes) != t.ans {
			panic("error")
		}
	}
	fmt.Println("success")
}

题目3.检查边长度限制的路径是否存在 §

题目描述 §

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。

给你一个查询数组 queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。

请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

测试链接 §

1697.检查边长度限制的路径是否存在

答案 §

var (
	father []int
)
 
func distanceLimitedPathsExist(n int, edgeList [][]int, queries [][]int) []bool {
	sort.Slice(edgeList, func(i, j int) bool {
		return edgeList[i][2] < edgeList[j][2]
	})
	// 排序前先记录原索引
	for i := range queries {
		queries[i] = append(queries[i], i)
	}
	sort.Slice(queries, func(i, j int) bool {
		return queries[i][2] < queries[j][2]
	})
	build(n)
	m := len(edgeList)
	k := len(queries)
	ans := make([]bool, k)
	j := 0 // 边的编号
	for _, q := range queries {
		for ; j < m && edgeList[j][2] < q[2]; j++ {
			union(edgeList[j][0], edgeList[j][1])
		}
		ans[q[3]] = isSameSet(q[0], q[1])
	}
	return ans
}
 
func build(n int) {
	father = make([]int, n+1)
	for i := range father {
		father[i] = i
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	father[find(a)] = find(b)
}
 
func isSameSet(a, b int) bool {
	return find(a) == find(b)
}

题目4.繁忙的都市 §

题目描述 §

一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造

城市的道路是这样分布的：城市中有 n 个交叉路口，有些交叉路口之间有道路相连

两个交叉路口之间最多有一条道路相连接，这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了

每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造

但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来
2. 在满足要求 1 的情况下，改造的道路尽量少
3. 在满足要求 1、2 的情况下，改造的那些道路中分值最大的道路分值尽量小

作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建，返回选出了几条道路以及分值最大的那条道路的分值是多少

测试链接 §

P2330【SCOI2005】繁忙的都市

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)
 
const (
	MAXN = 301
	MAXM = 8001
)
 
var (
	n int
	m int
	// [from, to, weight]
	edges  = [MAXM][3]int{}
	father = [MAXN]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		for i := 0; i < m; i++ {
			in.Scan()
			edges[i][0], _ = strconv.Atoi(in.Text())
			in.Scan()
			edges[i][1], _ = strconv.Atoi(in.Text())
			in.Scan()
			edges[i][2], _ = strconv.Atoi(in.Text())
		}
		sort.Slice(edges[:m], func(i, j int) bool {
			return edges[i][2] < edges[j][2]
		})
		ans := 0
		edgeCnt := 0
		for _, edge := range edges {
			if union(edge[0], edge[1]) {
				ans = max(ans, edge[2])
				edgeCnt++
			}
			if edgeCnt == n-1 {
				break
			}
		}
		fmt.Fprintf(out, "%d %d\n", edgeCnt, ans)
	}
	out.Flush()
}
 
func build() {
	for i := 1; i <= n; i++ {
		father[i] = i
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) bool {
	af := find(a)
	bf := find(b)
	if af == bf {
		return false
	}
	father[af] = bf
	return true
}