MST

最小生成树(MST:minimum-cost spanning tree)也称最小支撑树，任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通). 加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.最小代价生成树是其所有生成树中代价最小的生成树。

Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。

https://www.luogu.com.cn/problem/P3366

Prim算法

这里的代码去掉了select数组，使用dist数组来确定是否在MST内。因为MST内的点的dist值总是置为0。

#include<bits/stdc++.h>

//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'

#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long

const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;

struct {
    int to, w, next;
} edge[MAXN * 2];
int head[MAXN], dist[MAXN];
int cnt = 0;
int n;
int x, y, m, z;

void add(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}


int prim() {
    int now = x, minn, ans = 0, tot = 0;
    fill(dist, dist + MAXN, inf);
    for (int i = head[now]; i != -1; i = edge[i].next) {
        dist[edge[i].to] = min(dist[edge[i].to], edge[i].w);
    }
    while (++tot < n) {
        dist[now] = 0;
        minn = inf;
        now = -1;
        for (int i = 1; i <= n; ++i) {
            if (dist[i] && minn > dist[i]) {
                minn = dist[i];
                now = i;
            }
        }
        if (now == -1) {
            ans = -1;
            return ans;
        }

        ans += minn;

        for (int i = head[now]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (dist[v] > edge[i].w && dist[v]) {
                dist[v] = edge[i].w;
            }
        }

    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    while (m--) {
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    int res = prim();
    if (res == -1) { print("orz"); } else print(res);
    
}

Kruskal算法，按边权值排序后加边，在判断是否成圈时用到了并查集。

#include<bits/stdc++.h>
//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;

int Rank[MAXN], fa[MAXN];

inline void init(int n) {
    for (int i = 1; i < n; ++i) {
        fa[i] = i;
        Rank[i] = 1;
    }
}

int find(int x) {
    if (x == fa[x])
        return x;
    else {
        fa[x] = find(fa[x]);  //路径压缩+按秩合并有些时候可能并不适合
        return fa[x];
//        return find(fa[x]);
    }
}

inline void merge(int i, int j) {
    int x = find(i), y = find(j);    //先找到两个根节点
    if (Rank[x] <= Rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (Rank[x] == Rank[y] && x != y)
        Rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

struct Edge {
    int u, v, w;
} edge[MAXN];


bool cmp(Edge e1, Edge e2) {
    return e1.w < e2.w;
}

int cnt = 0;
int n;
int x, y, m, z, ans = 0;

int kruskal() {
    sort(edge, edge + m, cmp);
    init(n);
    int u, v, w;
    for (int i = 0; i < m; ++i) {
        u = edge[i].u;
        v = edge[i].v;
        w = edge[i].w;
        if (find(u) == find(v))continue;
        merge(u, v);
        ans += w;
        cnt++;
        if (cnt == n - 1)break;
    }

    if (cnt == n - 1)return ans;
    else
        return -1;
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y >> z;
        edge[i].u = x;
        edge[i].v = y;
        edge[i].w = z;
    }
    int res = kruskal();
    if (res == -1) { print("orz"); } else print(res);
}