定义#

最小生成树是指在一张无向图中，选取一些边，使其满足以下条件：

选择的边能够使图中的每一个节点直接或间接相连
在满足条件 1 的前提下，使得所有边的和尽可能小．（即获得连通所有点的最小代价）

[!node]- 题目：P3366 最小生成树
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz．
输入格式#
第一行包含两个整数 $N,M$ ，表示该图共有 $N$ 个结点和 $M$ 条无向边．
接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$ ，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$ ．
输出格式#
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和．如果该图不连通则输出 orz．
数据范围#
对于 $100\%$ 的数据： $1\le N\le 5000$ ， $1\le M\le 2\times 10^5$ ， $1\le Z_i \le 10^4$ ．

kruskal 算法#

kruskal 算法的本质是贪心，主要分为以下几步

先将所有边按权值从小到大排序．
依次选择权值最小的边，如果这条边连接的两个端点不在同一个连通块（即不形成环），就将这条边加入生成树．
重复上述过程，直到选出 n-1 条边（n 为节点数），或者所有边都被处理完．
如果仍旧有点没有被连通，那么原图就不是连通图

判断两个边是否连通，常使用并查集．

时间复杂度： $O(m)$

标程——kruskal#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 5e3 + 100;
4
const int M = 2e5 + 100;
5
int n, m;
6

7
int f[N];
8

9
// 定义一条边
10
struct Edge
11
{
12
  // u表示边的起点
13
  // v表示边的终点
14
  // w表示边的权值
15
  int u, v, w;
16
  friend bool operator<(Edge a, Edge b)
17
  {
18
    return a.w < b.w;
19
  }
20
} e[M];
21

22
// 并查集模板
23
class DSU
24
{
25
public:
26
  // 初始化并查集
27
  void build(int size)
28
  {
29
    for (int i = 1; i <= size; i++)
30
    {
31
      f[i] = i;
32
    }
33
  }
34
  // 找到节点t的最顶端的父节点
35
  int find(int t)
36
  {
37
    if (f[t] != t)
38
      f[t] = find(f[t]);
39
    return f[t];
40
  }
41
  // 将节点a和节点b所在集合合并
42
  void merge(int a, int b)
43
  {
44
    int x = find(a), y = find(b);
45
    if (x != y)
46
      f[x] = y;
47
  }
48
  // 查询a和b是否处于同一集合
49
  bool query(int a, int b)
50
  {
51
    return find(a) == find(b);
52
  }
53
} dsu;
54

55
void kruskal()
56
{
57
  // 进行排序
58
  sort(e + 1, e + m + 1);
59
  int ans = 0;
60
  // 依次选取每一条边，尝试添加
61
  for (int i = 1; i <= m; i++)
62
  {
63
    int u = e[i].u, v = e[i].v;
64
    if (!dsu.query(u, v))
65
    {
66
      ans += e[i].w;
67
      dsu.merge(u, v);
68
    }
69
  }
70
  // 判断是否连通
71
  for (int i = 1; i <= n; i++)
72
  {
73
    if (!dsu.query(1, i))
74
    {
75
      cout << "orz" << endl;
76
      return;
77
    }
78
  }
79
  cout << ans << endl;
80
  return;
81
}
82

83
int main()
84
{
85
  cin >> n >> m;
86
  for (int i = 1; i <= m; i++)
87
  {
88
    cin >> e[i].u >> e[i].v >> e[i].w;
89
  }
90
  dsu.build(n);
91
  kruskal();
92
}

prim 算法#

Prim 算法也是一种贪心．

核心思想：

从任意一个点出发，每次选择一条连接已选点集和未选点集、权值最小的边，将新点加入生成树．
重复 n-1 次，直到所有点都被包含．

常用优先队列（堆）优化，时间复杂度 $O(m\log n)$ ．

适合稠密图，代码实现类似 Dijkstra，但 Prim 关注的是“连通所有点的最小代价”，不是最短路．

标程——prim#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 5e3 + 100;
4
const int M = 2e5 + 100;
5
int n, m;
6

7
struct Edge
8
{
9
  int to, w;
10
  friend bool operator<(Edge a, Edge b)
11
  {
12
    return a.w > b.w;
13
  }
14
};
15

16
vector<Edge> e[N];
17
bool mark[N];
18

19
void prim()
20
{
21
  int ans = 0;
22
  priority_queue<Edge> q;
23
  q.push({1, 0});
24
  while (!q.empty())
25
  {
26
    int v = q.top().to, w = q.top().w;
27
    q.pop();
28
    if (mark[v])
29
      continue;
30
    mark[v] = true;
31
    ans += w;
32
    for (int i = 0; i < e[v].size(); i++)
33
    {
34
      q.push(e[v][i]);
35
    }
36
  }
37
  for (int i = 1; i <= n; i++)
38
  {
39
    if (!mark[i])
40
    {
41
      cout << "orz";
42
      return;
43
    }
44
  }
45
  cout << ans;
46
  return;
47
}
48

49
int main()
50
{
51
  cin >> n >> m;
52
  for (int i = 1; i <= m; i++)
53
  {
54
    int u, v, w;
55
    cin >> u >> v >> w;
56
    e[u].push_back({v, w});
57
    e[v].push_back({u, w});
58
  }
59
  prim();
60
}

音乐

音乐

定义#

输入格式#

输出格式#

数据范围#

kruskal 算法#

标程——kruskal#

prim 算法#

标程——prim#

文章分享