前置知识和定义

在开始学习最小生成树之前，先了解一些前置知识。

子图

对于一张图 $G=(V,E)$，如果存在一张图 $H=(V’,E’)$ 满足 $V’\subseteq V$ 且 $E’\subseteq E$，则称 $H$ 是 $G$ 的一个子图。记作 $H\subseteq G$。

生成子图

如果存在 $H \subseteq G$ 满足 $V’=V$，则称 $H$ 是 $G$ 的一个生成子图。

生成子图又称为支撑子图。

生成树

生成树：一个无向连通图的生成子图,且同时要求是树。也即在图的边集选择了 $n-1$ 条边，将图中的所有顶点连接起来。

最小生成树

我们定义，一个无向连通图的 最小生成树，是指这个图中边权和最小的生成树。

Kruskal 算法

Kruskal 算法是一种常见简单的用于求最小生成树的算法。此算法的基本思想就是贪心的从小到大加入边。

算法流程

对图中的所有边按边权从小到大排序。
从小到大枚举每一条边 $(u,v)$，如果 $u$ 和 $v$ 不在同一连通块中，就加入这条边，并将 $u$ 和 $v$ 所在的连通块合并。
重复步骤 2 直到加入了 $n-1$ 条边。

显然，我们需要使用并查集来维护每个点所在的连通块。那么，此算法的时间复杂度就为 $O(m\log m)$，其中 $m$ 是边数。

证明

归纳法证明

我们使用数学归纳法证明 Kruskal 算法的正确性。

基础：算法开始前，显然成立。

归纳：假设算法在加入了 $k-1$ 条边后，生成了一个最小生成树 $T$。我们需要证明，加入第 $k$ 条边 $(u,v)$ 后，生成的最小生成树 $T’$ 也成立。

我们可以分两种情况讨论：

如果 $(u,v)$ 不在 $T$ 中，那么 $T’$ 就是 $T$ 加上 $(u,v)$ 这条边。显然，$T’$ 是一个最小生成树。
如果 $(u,v)$ 在 $T$ 中，那么 $T’$ 就是 $T$ 去掉 $(u,v)$ 这条边，加上 $(u,v)$ 这条边的最小生成树。根据归纳假设，$T$ 是一个最小生成树，所以 $T’$ 也是一个最小生成树。

反证法

我们使用反证法证明 Kruskal 算法的正确性。

假设 Kruskal 算法得到的生成树 $T$ 不是最小生成树，那么必然存在某个最小生成树 $T_{opt}$，使得 $w(T_{opt}) < w(T)$，其中 $w(\cdot)$ 表示生成树的边权和。

设 $e_k = (u,v)$ 是 Kruskal 算法选择的第一个不在 $T_{opt}$ 中的边（按边权从小到大排序后的第 $k$ 条边）。由于 Kruskal 算法会选择这条边，说明在加入 $e_k$ 之前，$u$ 和 $v$ 不在同一个连通块中。

现在考虑 $T_{opt} \cup {e_k}$，这个图必然包含一个环（因为 $T_{opt}$ 是生成树，加入任何边都会形成环）。这个环中至少包含一条边 $e’$ 满足 $w(e’) \geq w(e_k)$（因为 $e_k$ 是连接这两个连通块的最小权边）。

我们可以构造一个新的生成树 $T’ = T_{opt} \cup {e_k} \setminus {e’}$。显然：

$T’$ 仍然是一个生成树（因为去除了环中的一条边）
$w(T’) = w(T_{opt}) + w(e_k) - w(e’) \leq w(T_{opt})$（因为 $w(e_k) \leq w(e’)$）

但是这与 $T_{opt}$ 是最小生成树的假设矛盾，因为我们找到了一个权值不大于 $T_{opt}$ 的生成树 $T’$，且 $T’$ 包含了 $e_k$。

通过重复这个过程，我们可以证明 Kruskal 算法得到的生成树 $T$ 必须是最小生成树，从而证明了算法的正确性。

代码实现

#include <bits/stdc++.h>
using namespace std;
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 2e5 + 100;
const int INF = 1e9;
const int mod = 1e9 + 7;
int T = 1, N, M;
int a[MaxN];
// vector<PII> G1[MaxN];
struct edge
{
    int x, y, z;
} e[MaxN];
bool cmp(edge a, edge b)
{
    return a.z < b.z;
}
int fa[MaxN];
struct MST
{
    vector<int> fn;
    MST(int n)
    {
        for (int i = 0; i <= n; i++)
        {
            fn.push_back(i);
        }
    }
    int find(int x)
    {
        if (fn[x] == x)
        {
            return x;
        }
        return fn[x] = find(fn[x]);
    }
    void join(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (fx != fy)
        {
            fn[fx] = fy;
        }
    }
    void kruskal(){
        int cnt=0,ans=0;
        sort(e+1,e+M+1,cmp);
        for(int i=1;i<=M;i++){
            int u=find(e[i].x);
            int v=find(e[i].y);
            if(u==v)continue;
            fn[u]=v;
            ans+=e[i].z;
            cnt++;
            if(cnt>N-1)break;
        }
        if(cnt==N-1){
            cout<<ans<<endl;           
        }
        else{
            cout<<"orz"<<endl;
        }
    }
};
inline void Solve()
{
    cin >> N >> M;
    MST mst(N);

    for (int i = 1; i <= M; i++)
    {
        cin >> e[i].x >> e[i].y >> e[i].z;
    }
    mst.kruskal();
}
signed main()
{
#ifdef NOI_IO
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

Prim 算法

Prim 算法是另一种常见的求最小生成树的算法，它的基本思想是从一个点开始，不断加点。

算法流程

选择图中的任意一个点作为起点，将其加入生成树。
从生成树中选择一个点 $u$，将 $u$ 到其他所有点的边加入候选边集合。
从候选边集合中选择一条边 $(u,v)$，权值最小，将 $v$ 加入生成树。
重复步骤 2 和 3，直到生成树包含所有点。

优化

如果直接暴力枚举所有边，时间复杂度是 $O(n^2)$，但是我们可以使用类似堆优化Dijkstra的方法，将时间复杂度优化到 $O(m\log n)$。

代码实现

#include <bits/stdc++.h>
using namespace std;
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int T = 1, N, M;
vector<PII> G1[MaxN];
int dist[MaxN];
bool vis[MaxN];
inline void Solve()
{
    cin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G1[u].push_back({v, w});
        G1[v].push_back({u, w});
    }
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    pq.push({0, 1});
    int ans = 0;
    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        ans += d;
        for (auto [v, w] : G1[u])
        {
            if (!vis[v] && dist[v] > w)
            {
                dist[v] = w;
                pq.push({w, v});
            }
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        if (!vis[i])
        {
            cout << "orz" << endl;
            return;
        }
    }
    cout << ans << endl;
}
signed main()
{
#ifdef NOI_IO
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}