最小生成树模板

prim算法

算法思想:每次选定未进入集合中和集合距离最小的点，用该点更新其他点到集合的距离，直到可以判断出不存在最小生成树或所有点均已进入集合
下面虽然是两种写法，但是记忆时最好还是按照算法的思路来实现，也就是第2个代码。虽然会多一些边界处理，但是只要我们理解了算法思想即使忘记了代码也能够自己实现出来

/**
 * 不需要每次都用集合中的点去找距离集合最近的点
 * 可以维护每个点到集合的距离，可以节省很多时间
 * 
 * 每次找到距离集合最近的点，加入到集合中，然后用该点更新其它点到集合的距离，每次操作向集合中加入一个点，一共n个点所以一共需要迭代n次
 * 
 * 本题为稠密图，所以采用邻接矩阵存储
 */

// 不太符合算法思想的写法，但是可以减少一些判断条件
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int dis[N]; // 之前的dis表示某点距离起点的距离，此时表示某点距离集合的距离
bool vis[N]; // 表示某个点是否在集合中
int g[N][N];

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    /**
     * 关于dis[1]的初始化问题
     * 按照该算法的逻辑来讲，不应该初始化这个点
     * dis[1] = 0表示1号点已经位于集合内了
     * 但是初始状态集合中应该为空
     * 不过这么写答案是正确的并且可以减少一下判断条件，只是和算法思想有些不符
     */
    dis[1] = 0;
     
    int res = 0;
    for (int i = 0; i < n; ++ i) // 每次将一点放入集合
    {
        // 找到未在集合且距集合最近的点
        int t = -1;
        for (int j = 1; j <= n; ++ j)
            if (!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        
        // 将该点放入集合并累加答案
        vis[t] = true;
        if (dis[t] == INF) return -1; // 说明目前找到的距离集合最近的点已经是无穷远的点了，说明无法构成一棵最小生成树
        res += dis[t];
    
        // 用该点更新其它节点距离集合的距离
        for (int j = 1; j <= n; ++ j)
            dis[j] = min(dis[j], g[t][j]); // 因为此时t已经进入了集合，所以和t相连的j点距离集合的距离就是j点距离t点的距离
    }
     
    return res;
}
int main()
{
    cin >> n >> m;
    // memset(g, 0x3f, sizeof g);
    /**
     * 对于g的初始化问题
     * 朴素版dijkstra和Floyd都采用的是邻接矩阵
     * dijkstra全部初始为无穷大
     * Floyd自己到自己初始化为0，其它初始化为无穷大
     * 怎么初始化完全要看算法执行过程对这些数据的要求
     * 按照我们在prim中的写法dis[j] = min(dis[j], g[t][j])
     * 可以发现用到自己到自己距离时说明t已经进入集合了，那么它的dis正确与否已经无所谓了，并不会影响到其它点到集合的距离，所以自己到自己不用初始化也可以
     */
     while (m --)
     {
         int a, b, k;
         cin >> a >> b >> k;
         g[a][b] = g[b][a] = min(g[a][b], k);
     }
     
     int t = prim(); // t表示返回的最小生成树的树边权重之和，-1表示最小生成树不存在
     
     if (t == -1) cout << "impossible" << endl;
     else cout << t << endl;
     
     return 0;
}

// 符合算法思想的写法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int dis[N];
bool vis[N];
int g[N][N];

int prim()
{
    memset(dis, 0x3f, sizeof dis); // 初始化dis[1] = 0并不会使答案发生改变，因为第一个点无论距离集合的距离为多少，总是会进入集合的，并且用它更新其它点时也不会用到自己的dis，所以无影响，但是从实际意义角度来讲不应该赋值0
    int res = 0;
    for (int i = 0; i < n; ++ i)
    {
        // 寻找距离集合距离最小的点
        // 所有距离都是无穷大，那么无穷大就是最小距离，我这思维定势了，觉得无穷大就不会是距离最小的点
        int t = -1;
        for (int j = 1; j <= n; ++ j)
            if (!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
                
        if (i && dis[t] == INF) return INF; // 不存在最小生成树的条件也是找到的最小距离都是无穷远，但是第一个点的距离肯定是INF，所以需要特判一下
        vis[t] = true;
        if (i) res += dis[t]; // 因为第一个点的dis是无穷大，所以不能累加到答案上,本身第一个点到集合的距离就是0，所以加不加无所谓
        
        for (int j = 1; j <= n; ++ j)
            dis[j] = min(dis[j], g[t][j]);
    }
    
    return res;
}
int main()
{
    memset(g, 0x3f, sizeof g); // 从使用g的位置可以看出，即使g[i][i]这种没更新答案也不会受到影响，其实更新了肯定不会错，如果不知道需不需要初始化那就写上，总不会错
    cin >> n >> m;
    while (m --)
    {
        int a, b, k;
        cin >> a >> b >> k;
        g[a][b] = g[b][a] = min(g[a][b], k);
    }
    
    int t = prim();

    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;
    
    return 0;
}

Kruskal算法

/**
 * Kruskal算法的理论思路
 * 首先对所有边从小到大排序，然后遍历所有边，如果该边的加入不会使得树中出现回路，那么就加入这条边
 * 
 * Kruskal算法的实现思路
 * 理论思想中边的排序和遍历都很好实现，难点就在于如何判断该边的加入会不会出现回路
 * 假设点a和b已经连通了，如果再在a和b之间连一条边那么势必就产生回路
 * 所以代码实现中只需要判断一条边的两个端点是否已经连通，是则不加入这条边，否则加入
 */
 
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

struct Edge {
    int a, b, w;
}edges[M];

int n, m;
int p[N];

int find(int u)
{
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}
int kruskal()
{
    int res = 0, cnt = 0; // res:最小生成树的权重之和 cnt:最小生成树中边数，负责判断是否存在最小生成树
    
    // kruskal第一步：将所有边按照权值从小到大排序
    sort(edges, edges + m, [](Edge a, Edge b) {return a.w < b.w;});
    
    // kruskal第二步：遍历所有边，将符合条件的边加入集合中
    for (int i = 0; i < m; ++ i)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int pa = find(a), pb = find(b);
        
        if (pa != pb)
        {
            p[pa] = pb;
            res += w;
            ++ cnt;
        }
    }
    
    if (cnt == n - 1) return res; // n个点的最小生成树有n-1条边
    else return INF;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++ i)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    for (int i = 1; i <= n; ++ i) p[i] = i; // 并查集初始化
    
    int t = kruskal();
    
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;
    
    return 0;
}