1.AcWing 1140. 最短网络 - AcWing（连通图求最小生成树）
连通图中求最小生成树建议使用 prime
算法解析：prime 有点类似dijkstra，每次选一个离集合最近的点去加入集合，然后拿这个点去更新剩下连通块中点到这个点的距离，因为这个点在集合中，这个距离也是代表到集合中距离，更新n次后n个点加入到集合中，我们每次拿到的 距离(距离集合最近的点到集合的距离)之和就是最小生成树的大小
算法实现如下：
int prime() {
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
int res = 0;
for (int i = 1; i <= n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j)
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
res += dist[t];
for (int j = 1; j <= n; ++j)
if(!st[j])dist[j] = min(dist[j],g[t][j]);
}
return res;
}
2.1141. 局域网 - AcWing题库（在非连通图中求多个连通块中的最小生成树）
多个连通块中求多个最小生成树建议使用Kruskal
算法 解析：
Kruskal算法：
1.先将所有边权从小到大排序
2.依次去枚举每条边 a，b，w，如果a和b不连通，
那么就将当前边加入到最小生成树中去
算法核心： 首先题目保证存在生成树(所有点是连通的)
当我们从小到大拿到一条边对应的两点发现他们是不连通的
我们就可以将他们直接连通的边更新为这条边--把他们连通
这条边也就是最小生成树的边
代码实现：
int res = 0;
for (int i = 0; i < m; ++i) {
int a = find(e[i].a), b = find(e[i].b);
if (a != b){
p[a] = b;
res += e[i].w;
}
}
当然，头铁多个连通块求最小生成树也是可以用prime的 （借用本题第二个大佬 Fighting_Peter ,的题解）
思路解析：在原有的prime算法前加一个for，遍历1-n所有点作为起点的连通块
if st[k]==true ，表示第k个点已经在之前的最小生成树当中了，则continue掉
else 就是一个新的连通块 ，允许他进去更新他这个连通块的内容
int prime() {
for (int k = 1; k <= n; ++k) {
//遍历所有点为起点找连通块，看看他是否已经在一个连通块中
if (st[k])continue;
memset(dist,0x3f,sizeof dist);
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j)
if (!st[j] && (t == -1 || dist[j] < dist[t]))t = j;
st[t] = true;
for (int j = 1; j <= n; ++j)
if (!st[j])dist[j] = min(dist[j],g[t][j]);
}
for (int i = 1; i <= n; ++i)
if (dist[i] < 0x3f3f3f3f)res += dist[i];
}
return res;
}
这里的res也就是最小生成树的大小
3.AcWing 1142. 繁忙的都市 - AcWing -- 非常简单的一道题目，也就是Kruskal的另一个应用
求最小生成树中最大的一条边
4.AcWing 1143. 联络员（算法提高课） - AcWing --这题依然很简单-- 就是Kruskal的选择性插入
5.AcWing 1144. 连接格点 - AcWing
本题思路也比较清晰，但是要注意一些细节处理
题意：给你几条已知边--必选，让你找找至少还需要插入多少权重的边才能形成一颗最小生成树
思路： 和4一样先必选几条边，然后再剩余的边中找到最合适的边插入最小生成树
本体难点：
1.二维化一维，下标从1开始，可以用如下代码实现
for (i = 1, t = 1; i <= n; ++i) for (int j = 1; j <= m; ++j, ++t) g[i][j] = t;
2.由于Kruskal算法不会选择已经加入最短生成树的边，so我们寻找剩余边的时候全部初始化也没问题，因为，那些必选的边最后都会被筛掉，so我们的求所有边代码如下，竖边-1，横边-2
void get_edges() {//排序：先放纵向边--1 ，再放横向边--2
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }, dw[4] = { 1,2,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 = g[i][j], b = g[x][y];
if (a < b)e[k++] = { a,b,w };
}
}
}
//当然本题也可以不化为一维自己 写一个二维find即可--详情请看本题链接中第二个大佬ZTEG 的题解
