3.3.1 最小生成树的典型应用

Prim 算法

从某一个点开始, 逐渐去把所有点和这个点连通起来, 每次选择这个点所在的连通块和外界最近的点加入到连通块中, 扩展n - 1次

Kruskal算法

将所有边从小到大排序, 每次从小到大枚举所有边. 左边的点, 可能在一个连通块, 右边的点可能在另外的连通块.
当前的边有好几种情况:

正确性:
如果在最优解中没有使用这条边, 由于我们在考虑前面所有边的时候, 这两个点都是不连通的, 因此最终这两个必然是连通的, 假设红色虚线是连通的路径, 由于前面的边不能将这两个点连通, 因此在这个环上必然有在后面的一条边, 由于我们是按照边权从小到大排序的, 因此红色边的权重一定>=蓝色边的权重, 同样, 可以删去红色边, 加入蓝色边, 这样还是一棵生成树, 并且结果不会变差, 因此蓝色边一定可以在最优解中.

如果证明当前这条边一定可以被选?
假设不选当前边, 最终得到了一棵树. 然后将这条边加上, 那么必然出现一个环, 在这个环, 一定可以找出长度不小于当前边的边, 那么把当前边替换上去, 结果一定不会变差

AcWing 1140. 最短网络

分析

n个点, $\frac{n(n-1)}{2}$条边, 已知任意两点之间的距离, 求将所有点连通起来的最小需要耗费的边权之和是多少
裸的最小生成树算法
给的是裸的邻接矩阵数据, 直接Prim

code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N], dist[N];
int n, m;
bool st[N];

int prim(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;
    
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        
        st[t] = true;
        res += dist[t];
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }
    return res;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    
    int t = prim();
    cout << t << endl;
    return 0;
}

AcWing 1141. 局域网

分析

给了n个点和k条边的图, 图中可能存在环, 需要从中去掉边(但仍然需要保持连通性), 使得网络中没有回路.
相当于是在这个图的每个连通块内,((注意: 题目没有说明一开始所有点都是连通的), 一开始可能不是连通图, 可能是多个连通块,) 求一棵最小生成树. 相当于求原图的“最小生成森林”.
由于每个连通块是相互独立的, 因此对每个连通块来说, 要去掉尽可能大的边权(即:留下的边权之和最小->最小生成树).

Prim算法不太好写, 因为每次只能处理一个连通块. 如果要处理多个连通块, 要多次调用Prim.
因此用Kruskal比较好写.
步骤:
做Kruskal算法

1. 将所有边权从小到大排序
2. 依次枚举每条边a, b, w
   2.1 如果a, b不连通, 那么就将当前边加入到最小生成树中去

   如果不用这条边, 这两个点必然通过其他点连通, 将蓝色边加上, 必然存在蓝色边之后的某条边(红边), 红边权值 >= 蓝边, 删红边, 加蓝边, 也得到了一棵生成树, 总共的边权之和不会变差.
   

code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 220;
struct Edge{
    int a, b, w;
    bool operator < (const Edge &W) const {
        return w < W.w;
    }
}edge[M];
int n, m;
int p[N];

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

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ){
        scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].w);
    }
    
    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int res = 0;
    
    for (int i = 0; i < m; i ++ ){
        int a = edge[i].a, b = edge[i].b, c = edge[i].w;
        a = find(a), b = find(b);
        if (a != b) p[a] = b;
        else res += c;
    }
    
    cout << res << endl;
    
    return 0;
}

1142. 繁忙的都市

分析

1. 改造的道路能够把所有道路连通起来(连通性)
2. 改造的道路尽量少-> 必然是求一棵树(因为有n个点, 最少需要n - 1条边才能将点连通起来 )
   证明by :

Show that every connected graph with n vertices has at least n − 1 edges.
证明每个有n个顶点的连通图都至少有n-1条边
证明：不妨设G是无向连通图（若G为有向图，可忽略边的方向讨论对应的底图）。
设G中顶点为v1, v2, …, vn。由连通性，必存在与v1相邻的顶点，不妨设其为v2（否则，可重新编号），连接v1与v2得边e1，还是由连通性，在v3, v4, …, vn中必存在与v1或v2相邻的顶点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1, v2, …, vn-1中的某顶点相邻，得新边，由此可见G中至少有n-1条边。

而有关正整数n的命题通常可以用数学归纳法加以证明
归纳基础：0、1显然成立。
归纳假设：带有k个顶点的连通图至少具有k-1条边。
下面我们来证明带有k+1个顶点的连通图至少具有k条边。我们把k+1个顶点分成两部分，一部分含有k个顶点，一部分只有一个顶点，对于k个顶点的连通图我们知道它至少具有k-1条边，我们只需要这样构造：把那个孤立的顶点与k个顶点中的任何一个连接形成一条边，那么显然带有k+1个顶点的连通图至少具有k条边。

3. 改造哪些道路中分值最大值尽量小 ->

普通的最小生成树: 所有边权之和最小
本题中的最小生成树: 最大的边权最小
最大边权最小 直觉上可以用二分.
首先先将边权排序, 将所有的边列出来, 二分最大值, 去判断在二分值左边的这些边能否将点连通(bfs, dfs都可以判断连通性, 并查集也可以, 时间复杂度mlogL, L是边权最大值)
考虑最小生成树做法:

1. 将所有边从小到大排序
2. 从小到大一次枚举每条边, a, b, w
   2.1 如果a, b已经连通, 那么直接pass
   2.2 如果a, b不连通, 那么就将当前边算选出来.
   当我们将最后一条边加进来的时候, 前面 n - 1条边, 前面n - 1条边一定是最优解, 那么最后一条边就是我们的答案

code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310, M = 8010;
struct Edge{
    int a, b, w;
    bool operator < (const Edge &W) const{
        return w < W.w;
    }
}e[M];
int n, m, p[N];
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < m ; i ++ ){
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].w);
    }
    
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    sort(e, e + m);
    int res;
    
    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 << n - 1 << ' ' << res << endl;
    return 0;
}

1143. 联络员

分析

必选的通信渠道: 如果出现必选的重边, 要加多次
直观的想法:
把所有必选的边选上, 把已经连通点看成一块, 当成一个整体来看, 相当于在变完的图上求最小生成树

1. 把所有必选边加到并查集中
2. 将所有非必选边从小到大排序
3. 从小到大依次枚举每一条非必选边 a, b, w
   3.1 如果a和b已经连通, pass
   3.2 如果a和b不连通, 那么就将当前边选上

code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010, M = 10010;
struct Edge{
    int a, b, w;
    bool operator <(const Edge &W){
        return w < W.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];
}

int main(){
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int res = 0, k = 0;
    for (int i = 0; i < m; i ++ ){
        int t, a, b, w;
        cin >> t >> a >> b >> w;
        if (t == 1){
            res += w;
            p[find(a)] = find(b);
        }else e[k ++ ] = {a, b, w};
    }
    
    sort(e, e + k);
    for (int i = 0; i < k; 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;
    
    return 0;
}

AcWing 1144. 连接格点

分析

感觉和上一题一样, 有些点已经有连线, 求连通所有点的最小花费(因为边权为正, 树的数据结构边数最少, 因此就是在问求最小生成树)
另外一个问题: n个点, m条边, 无向图, 边权可正可负, 求连通所有点的最小花费 (❌ 最小生成树)
考虑完全图: 那么我们应该将所有边全部选上, 多一条边可以将边权之和降低, 因此不是最小生成树问题
横向边 (m - 1) * n 纵向边 (n - 1)m , 大概2nm条边 2000000条边, 排序的话, 没问题
但是如果题目有多组数据, 时间卡的比较紧, 那么我们可以先加纵向边, 再加横向边, 可以省去排序的过程
时间复杂度 $O(k\log k)\to O(k)$
二维问题需要转化成一维问题
将每个点标上一个号

code

ids[N][N]: 将2维坐标映射为1维的数组

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = N * N, K = 2 * N * N;
int n, m, k;

struct Edge{
    int a, b, w;
    bool operator < (const Edge &W){
        return w < W.w;
    }
}e[K];
int ids[N][N];
int p[M];

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

void get_edges(){
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, dw[] = {1, 2, 1, 2}; // dw边权, 纵向1, 横向2
    for (int z = 0; z < 2; z ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                for (int u = 0; u < 4; u ++ )
                    if (u % 2 == z){
                        int x = i + dx[u], y = j + dy[u], w = dw[u];
                        if (x && x <= n && y && y <= m){
                            int a = ids[i][j], b = ids[x][y];
                            if (a < b) e[k ++ ] = {a, b, w}; // 边只加一次,就可以了 (a < b)保证重复的边只加1次
                        }
                    }
}


int main(){
    cin >> n >> m;
    // 2维->1维
    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);
    }
    
    get_edges();
    
    int res = 0;
    for (int i = 0; i < k; 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;
    return 0;
}