python/TangDou/Topic/【最小生成树】专题.md

## 最小生成树专题

$Prim$算法和$Kruskal$算法都是用于 **求解最小生成树的算法**，但它们的使用场景和应用领域存在一些差异。

### 一、算法概述

#### $Prim$算法
① $Prim$算法是一种贪心算法，基于顶点的方式构建最小生成树。
② $Prim$算法 **适用于稠密图**，即边的数量接近于完全图$(n*(n-1)/2)$的图。
③ $Prim$算法从一个起始顶点开始逐步扩展，直到生成一个包含所有顶点的最小生成树。
④ $Prim$算法的时间复杂度为$O(ElogV)$，对于稠密图有较好的性能。

**[$AcWing$ $858$. $Prim$ 算法求最小生成树](https://www.cnblogs.com/littlehb/p/15330282.html)**

**$Code$模板**
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N]; // 稠密图，邻接矩阵
int dis[N];  // 这个点到集合的距离
bool st[N];  // 是不是已经使用过
int res;     // 最小生成树里面边的长度之和
int pre[N];  // 前驱结点

// 普利姆算法求最小生成树
int prim() {
    memset(dis, 0x3f, sizeof dis);
    memset(pre, -1, sizeof pre); // 记录前驱路径
    dis[1] = 0;

    for (int i = 0; i < n; i++) { // 迭代n次
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j;
        if (i && dis[t] == INF) return INF; // 非连通图，没有最小生成树
        if (i) res += dis[t];
        for (int j = 1; j <= n; j++)
            if (!st[j] && g[t][j] < dis[j]) {
                dis[j] = g[t][j];
                pre[j] = t; // 记录是由谁转移而来
            }
        st[t] = true;
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

    // 读入数据
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF)
        puts("impossible");
    else
        cout << t << endl;

    // 输出前驱结点
    for (int i = 1; i <= n; i++) printf("%d ", pre[i]);
    return 0;
}
```
#### $Kruskal$算法
① $Kruskal$算法是一种基于边的方式构建最小生成树的算法。
② $Kruskal$算法 **适用于稀疏图**，即边的数量远小于完全图$(n*(n-1)/2)$的图。
③ $Kruskal$算法按权值递增的顺序选择边，并通过判断是否构成环来决定是否将边加入最小生成树。
④ $Kruskal$算法的时间复杂度为$O(ElogE)$，对于稀疏图有较好的性能。

**[$AcWing$ $859$. $Kruskal$ 算法求最小生成树](https://www.cnblogs.com/littlehb/p/15336857.html)**

**$Code$模板**
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 100010, M = N << 1;
const int INF = 0x3f3f3f3f;

int n, m; // n条顶点,m条边
int res;  // 最小生成树的权值和
int cnt;  // 最小生成树的结点数

// Kruskal用到的结构体
struct Node {
    int a, b, c;
    bool const operator<(const Node &t) const {
        return c < t.c; // 边权小的在前
    }
} edge[M]; // 数组长度为是边数

// 并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// Kruskal算法
void kruskal() {
    // 1、按边权由小到大排序
    sort(edge, edge + m);
    // 2、并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;
    // 3、迭代m次
    for (int i = 0; i < m; i++) {
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        a = find(a), b = find(b);
        if (a != b)
            p[a] = b, res += c, cnt++; // cnt是指已经连接上边的数量
    }
    // 4、特判是不是不连通
    if (cnt < n - 1) res = INF;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }
    kruskal();
    if (res == INF)
        puts("impossible");
    else
        printf("%d\n", res);
    return 0;
}
```

### 二、最小生成树练习题题单
#### [$AcWing$ $1140$. 最短网络](https://www.cnblogs.com/littlehb/p/16043987.html)
$Prim$或者$Kruskal$祼题,直接套模板即可

#### [$AcWing$ $1141$. 局域网](https://www.cnblogs.com/littlehb/p/16044103.html)
最小生成森林，需要注意与最小生成树的区别,两种方法，推荐使用$Kruskal$

#### [$AcWing$ $1142$. 繁忙的都市](https://www.cnblogs.com/littlehb/p/16044984.html)
$Kruskal$的简单应用,求分值最大的那条道路

#### [$AcWing$ $1143$. 联络员](https://www.cnblogs.com/littlehb/p/16048583.html)
$Kruskal$的简单应用，先把必选的边放到并查集中，然后将可选的边由小到大排序，再进行$Kruskal$即可。

#### [$AcWing$ $1144$. 连接格点](https://www.cnblogs.com/littlehb/p/16049186.html)
- 按边权先小后大建图，这样省的排序，当然，如果你愿意排序，顺序也不重要。
- 序号都是连着的，所以需要一个 `get(x,y)`的转换函数
- 注意最右边那列节点是无法向右引出边的，需要判断一下
- 现成的，必须有的边需要提前放到并查集中，其它的再跑$Kruskal$

### 三、最小生成树的扩展应用题单
#### [$AcWing$ $1146$. 新的开始](https://www.cnblogs.com/littlehb/p/16050831.html)
- 利用超级源点将点权转为边权
- 注意加入超级源点后，遍历的节点数量$+1$

#### [$AcWing$ $1145$. 北极通讯网络](https://www.cnblogs.com/littlehb/p/16053424.html)
- 魔改$Kruskal$算法，利它的框架，增加一点代码，检查剩余的连通块个数是不是$ \leq cnt$

#### [$AcWing$ $346$. 走廊泼水节](https://www.cnblogs.com/littlehb/p/16053808.html)
- 由最小生成树扩展成完全图，这是我们的知识盲区，没有这样的定理或算法
- 逆向思维，是不是可以由一个完全图思考如何求它的最小生成树？这可以用$Kruskal$算法！
- 对边权由小到大排序，一个个进行讨论，当第一个不在集合中的边出现时，此边将为最小生成树的一条边。
那么，对于两个家族的其它成员而言，要想形成完全图，就需要笛卡尔积条边，对了，还需要把这条最小生成树的边去掉才行。
- 加上去的那些边，条边最小都需要比当前枚举到的边长大$1$才行,因为这样才能保证求出的是唯一最小生成树，并且这种补全办法的成本最低！

**知识点**
① 并查集+维护个数
② 逆向思维
③ 最小生成树$Kruskal$算法

AcWing 1148. 秘密的牛奶运输