2025-02-06最小生成树的典型应用

最小生成树的典型应用

主要内容

1. 最小生成树的基本概念

  • 定义：在一个加权连通图中，最小生成树是一个包含图中所有顶点的子图，且边的总权重最小。
  • 应用场景：网络设计、城市规划、通信线路铺设等，目标是连接所有节点，同时最小化总成本。
  • 一般思路：

2. 最小生成树的两种主要算法

  • Prim算法

    • 适用场景：适用于稠密图（边数较多的图）。

    • 时间复杂度：O(n2)，可以通过堆优化降低到 O(mlogn)。

    • 核心思想：从一个起点开始，逐步扩展最小生成树，每次选择与当前生成树相连的最小权重边。

    • 代码实现：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      int prim() {
          int res = 0;
          memset(dist, 0x3f, sizeof dist);
          dist[1] = 0;

          for (int i = 0; i < n; i++) {
              int t = -1;
              for (int j = 0; j < n; j++) {
                  if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
              }

              res += dist[t];
              st[t] = true;

              for (int j = 0; j < n; j++) dist[j] = min(dist[j], w[t][j]);
          }

          return res;
      }
      CPP

  • Kruskal算法

    • 适用场景：适用于稀疏图（边数较少的图）。

    • 时间复杂度：O(mlogm)，其中 m 是边的数量。

    • 核心思想：将所有边按权重从小到大排序，依次选择不形成环的边加入最小生成树。

    • 代码实现：

      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
      int find(int x) {
          if (p[x] != x) p[x] = find(p[x]);
          return p[x];
      }

      void work() {
          cin >> n >> m;

          for (int i = 1; i <= n; i++) p[i] = i;

          for (int i = 0; i < m; i++) {
              int a, b, w;
              cin >> a >> b >> w;
              e[i] = {a, b, w};
          }

          sort(e, e + m);

          int res = 0;
          for (int i = 0; i < m; i++) {
              int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
              if (a != b) {
                  p[a] = b;
                  res += w;
              }
          }

          cout << res << endl;
      }
      CPP

3. 并查集的使用

  • 功能：用于管理不相交集合，支持快速合并和查找操作。

  • 核心操作：

    • 查找操作（Find）：通过路径压缩优化查找效率。
    • 合并操作（Union）：通过按秩合并优化合并效率。

  • 代码实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void union_sets(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA != rootB) {
            p[rootA] = rootB;
        }
    }
    CPP

4. 最小生成树的变种问题

  • 最大边权最小化：

    • 问题描述：在维持连通性的情况下，使最大边权最小。

    • 解决方案：使用Kruskal算法，记录最后加入的边的权重。

    • 代码实现：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      int max = -1, s = 0;
      for (int i = 0; i < m; i++) {
          int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
          if (a != b) {
              p[a] = b;
              s++;
              max = w;
          }
      }

      cout << s << " " << max << endl;
      CPP

  • 必选边和可选边：

    • 问题描述：某些边必须选择，某些边可以选择。

    • 解决方案：先处理必选边，再处理可选边。

    • 代码实现：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      int res = 0;
      for (int i = 0; i < m; i++) {
          int f, a, b, w;
          cin >> f >> a >> b >> w;
          if (f == 1) {
              int aa = find(a), bb = find(b);
              if (aa != bb) p[aa] = bb;
              res += w;
          } else {
              e[cnt++] = {a, b, w};
          }
      }

      sort(e, e + cnt);

      for (int i = 0; i < cnt; i++) {
          int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
          if (a != b) {
              res += w;
              p[a] = b;
          }
      }

      cout << res << endl;
      CPP

5. 二维坐标映射为一维数组

  • 问题描述：在某些问题中，需要将二维坐标映射为一维数组的下标。

  • 解决方案

    1
    2
    3
    4
    int ids[K][K];
    for (int i = 1, t = 1; i <= n; i++)
        for (int j = 1; j <= m; j++, t++)
            ids[i][j] = t;
    CPP

6. 总结

  • 最小生成树是图论中的一个重要概念，广泛应用于网络设计和资源优化。
  • Prim算法和Kruskal算法是两种常用的最小生成树算法，各有优劣，适用于不同类型的图。
  • 并查集是处理最小生成树问题时常用的辅助数据结构，支持高效的合并和查找操作。
  • 变种问题（如最大边权最小化、必选边和可选边）可以通过对标准算法的扩展来解决。
  • 二维坐标映射是处理网格问题时的常用技巧，可以简化问题的复杂度。

例题

最短网络

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
43
44
// https://www.luogu.com.cn/problem/P1546

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int n;
int w[N][N];
int dist[N];
bool st[N];

int prim(){
    int res=0;
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;

    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=0;j<n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        }

        res+=dist[t];
        st[t]=true;

        for(int j=0;j<n;j++) dist[j]=min(dist[j], w[t][j]);
    }

    return res;
}

void work(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>w[i][j];

    cout<<prim()<<endl;
}

int main(){
    work();
    return 0;
}
CPP

局域网

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
43
44
45
46
47
48
49
50
51
52
53
// https://www.luogu.com.cn/problem/P2820

/*
 * 注意这里不能保证所有计算机都连通，所以相当于在每个联通块内求最小生成树
 * 这里使用prim就比较麻烦，所以使用kruskal算法比较合适
 * 事实上，kruskal比prim更具有普适性
*/

#include<bits/stdc++.h>
using namespace std;

const int N=110, M=210;
struct Edge{
    int a, b, w;
    bool operator<(const Edge&t)const{
        return w<t.w;
    }
}e[M];
int n, m;
int p[N];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    cin>>n>>m;

    for(int i=1;i<=n;i++) p[i]=i;

    for(int i=0;i<m;i++){
        int a, b, w;
        cin>>a>>b>>w;
        e[i]={a, b, w};
    }

    sort(e, e+m);

    int res=0;
    for(int i=0;i<m;i++){
        int a=find(e[i].a), b=find(e[i].b), w=e[i].w;
        if(a!=b) p[a]=b;
        else res+=w;// 这里记录的是要删除的边
    }

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}
CPP

繁忙的都市

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
43
44
45
46
47
48
49
50
51
52
53
54
55
// https://www.luogu.com.cn/problem/P2330
/*
 * 朴素的最小生成树：求维持连通性的情况下，边权之和最小
 * 本题要求的是：维持连通性的情况下，最大边权最小
 * 事实上，用Kruskal算法一样能解决！
*/

#include<bits/stdc++.h>
using namespace std;

const int N=310, M=8010;
struct Edge{
    int a, b, w;
    bool operator<(const Edge&t)const{
        return w<t.w;
    }
}e[M];
int p[N];
int n, m;

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    cin>>n>>m;

    for(int i=1;i<=n;i++) p[i]=i;

    for(int i=0;i<m;i++){
        int a, b, w;
        cin>>a>>b>>w;
        e[i]={a, b, w};
    }

    sort(e, e+m);

    int max=-1, s=0;
    for(int i=0;i<m;i++){
        int a=find(e[i].a), b=find(e[i].b), w=e[i].w;
        if(a!=b){// 连上当前可选，连接这两点的最小的边，结果肯定是最优的
            p[a]=b;
            s++;// 统计有几条边
            max=w;// 最后一条肯定是最大的
        }
    }

    cout<<s<<" "<<max<<endl;
}

int main(){
    work();
    return 0;
}
CPP

联络员

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
43
44
45
46
47
48
49
50
51
52
53
54
55
// https://blog.csdn.net/m0_62597063/article/details/125855338
// http://ybt.ssoier.cn:8088/problem_show.php?pid=1393

#include<bits/stdc++.h>
using namespace std;

const int N=2010, M=10010;
struct Edge{
    int a, b, w;
    bool operator<(const Edge&t)const{
        return w<t.w;
    }
}e[M];
int p[N];
int n, m;

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    cin>>n>>m;

    for(int i=1;i<=n;i++) p[i]=i;

    int res=0, cnt=0;
    for(int i=0;i<m;i++){
        int f, a, b, w;
        cin>>f>>a>>b>>w;
        if(f==1){
            int aa=find(a), bb=find(b);
            if(aa!=bb) p[aa]=bb;// 注意并查集的“并”操作，一定要先定位到根节点，再做并
            res+=w;
        } 
        else e[cnt++]={a, b, w};
    }

    sort(e, e+cnt);

    for(int i=0;i<cnt;i++){
        int a=find(e[i].a), b=find(e[i].b), w=e[i].w;
        if(a!=b){
            res+=w;
            p[a]=b;
        }
    }

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}
CPP

连接格点

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// http://ybt.ssoier.cn:8088/problem_show.php?pid=1394

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10, M=2e6+10, K=1010;
struct Edge{
    int a, b, w;
    // bool operator<(const Edge&t)const{
    //     return w<t.w;
    // }
}e[M];
int ids[K][K];
int p[N];
int n, m;

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    cin>>n>>m;

    //这一步是将二维坐标映射成一维数组的下标，值得学习
    for(int i=1, t=1;i<=n;i++)
        for(int j=1;j<=m;j++, t++)
            ids[i][j]=t;

    for(int i=1;i<n*m;i++) p[i]=i;

    int x1, y1, x2, y2;
    while(cin>>x1>>y1>>x2>>y2){
        int a=ids[x1][y1], b=ids[x2][y2];
        p[find(a)]=find(b);
    }

    int cnt=0;
    for(int k=1;k<=m;k++)
        for(int i=1, j=2;j<=n;i++, j++){
            e[cnt++]={ids[i][k], ids[j][k], 1};
        }

    for(int k=1;k<=n;k++)
        for(int i=1, j=2;j<=m;i++, j++){
            e[cnt++]={ids[k][i], ids[k][j], 2};
        }

    /*
     * "还需要"， 所以必选的边权不用加进去
     * 把所有边扫一遍也无伤大雅，因为必选边添加之后，两点处于联通状态，再次遇到时会自动跳过
    */
    int res=0;
    for(int i=0;i<cnt;i++){
        int a=find(e[i].a), b=find(e[i].b), w=e[i].w;
        if(a!=b){
            res+=w;
            p[a]=b;
        }
    }

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}
CPP
寒假练题计划 > 提高算法 > 图论 > 最小生成树
#cpp #algorithm #ACwing #MST #Kruskal #Prim #Disjoint-set
2025-02-06最小生成树的典型应用
http://666xz666.github.io/2025/02/06/最小生成树的典型应用/
作者
666xz666
发布于
2025年2月6日
许可协议