Kruskal

路径压缩

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int MAXM = 200000;
struct Edge
{
    int u, v, w;
};
Edge e[MAXM + 5];
int n, m;
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int fa[MAXN + 5];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    // 并查集初始化
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    // kruskal 算法
    sort(e + 1, e + m + 1, cmp);
    int sum = 0, cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int faU = findFa(u);
        int faV = findFa(v);
        if (faU != faV)
        {
            fa[faU] = faV;
            sum += w;
            cnt++;
        }
    }
    if (cnt == n - 1)
        cout << sum;
    else
        cout << "orz";
    return 0;
}

路径压缩+启发式合并

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int MAXM = 200000;
struct Edge
{
    int u, v, w;
};
Edge e[MAXM + 5];
int n, m;
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int fa[MAXN + 5];
int cnt[MAXN + 5];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    // 并查集初始化
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        cnt[i] = 1;
    }
    // kruskal 算法
    sort(e + 1, e + m + 1, cmp);
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int faU = findFa(u);
        int faV = findFa(v);
        if (faU != faV)
        {
            if (cnt[faU] < cnt[faV])
            {
                fa[faU] = faV;
                cnt[faV] += cnt[faU];
            }
            else
            {
                fa[faV] = faU;
                cnt[faU] += cnt[faV];
            }
            sum += w;
        }
    }
    if (cnt[findFa(1)] == n)
        cout << sum;
    else
        cout << "orz";
    return 0;
}

Prim

优先队列 （$m\log{m}$）

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const int MAXN = 5000;
const int MAXM = 200000;
int n, m;
vector<pair<int, int>> e[MAXN + 5];
// 到树的距离
int dis[MAXN + 5];
// 在不在树上
bool vis[MAXN + 5];
// 快速找最近的 <距离,点的编号>
priority_queue<pair<int, int>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    // Prim
    for (int i = 1; i <= n; i++)
        dis[i] = INF, vis[i] = false;
    dis[1] = 0;
    pq.push({0, 1});
    int sum = 0, cnt = 0; // 边之和、边的条数
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        sum += dis[u];
        cnt++;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (w < dis[v])
            {
                dis[v] = w;
                pq.push({-dis[v], v});
            }
        }
    }
    if (cnt == n)
        cout << sum;
    else
        cout << "orz";
    return 0;
}

暴力 $O(n)$ 找最近，$O(n^2+m)$

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const int MAXN = 5000;
const int MAXM = 200000;
int n, m;
vector<pair<int, int>> e[MAXN + 5];
// 到树的距离
int dis[MAXN + 5];
// 在不在树上
bool vis[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    // Prim
    for (int i = 1; i <= n; i++)
        dis[i] = INF, vis[i] = false;
    dis[1] = 0;
    int sum = 0, cnt = 0; // 边之和、边的条数
    for (int T = 1; T <= n; T++)
    {
        int u = -1;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] || dis[i] == INF)
                continue;
            if (u == -1 || dis[i] < dis[u])
                u = i;
        }
        if (u == -1)
        {
            cout << "orz";
            return 0;
        }
        vis[u] = true;
        sum += dis[u];
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (w < dis[v])
                dis[v] = w;
        }
    }
    cout << sum;
    return 0;
}