最小生成树

Skyzhou666 · 2022-09-23 12:53:43 · 算法·理论

Kruskal

存边贪心+并查集

#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 100020
typedef long long LL;
using namespace std;

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

int n, m;
int fa[MAXN];
vector <edge> MST;

bool cmp(edge x, edge y)
{
    return x.w < y.w;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int Kruskal()
{
    for(int x = 1; x <= n; x++) fa[x] = x;
    int ans = 0;
    sort(g+1, g+m+1, cmp);
    for(int x = 1; x <= m; x++)
    {
        int u = find(g[x].u), v = find(g[x].v);
        if(u == v) continue;
        fa[v] = u;
        ans += g[x].w;
        MST.push_back(g[x]);
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    for(int x = 1; x <= m; x++)
        cin >> g[x].u >> g[x].v >> g[x].w;
    cout << Kruskal() << endl;
    for(edge x : MST) cout << x.u << " " << x.v << " " << x.w << endl;
    return 0;
}

然而luoguP3366还要用一个并查集判断图是否连通才能过（