Kruskal求最小生成树

运用了贪心的思想

最小生成树上的每条边一定是可选的最小边才能最优，其他情况均不是最优

因此将所有边加入小根堆，然后每次取堆顶

并查集维护连通性防止重复加边以及生成环

代码：

# include <iostream>
# include <cstdio>
# include <queue>
# include <cstring>
# define MAXN 300*300+5

using namespace std;

struct node{
    int u, v;
    int next;
    int val;
    bool operator > (const node that) const{
        return this->val > that.val;
    }
}a[MAXN], temp;

int head[MAXN], cntEdge, w, n, fa[305];
long long ans;

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

void merge(int x, int y){
    int fx = find(x), fy = find(y);
    fa[fy] = fx;
    return;
}

priority_queue <node,vector<node>,greater<node> > q;

void addEdge(int u, int v, int val){
    ++cntEdge;
    a[cntEdge].u = u;
    a[cntEdge].v = v;
    a[cntEdge].val = val;
    a[cntEdge].next = head[u];
    head[u] = cntEdge;
    return;
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        fa[i] = i;
        cin>>w;
        addEdge(0, i, w);
        q.push(a[cntEdge]);
    }   
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            cin>>w;
            if(i < j){
                addEdge(i, j, w);
                q.push(a[cntEdge]);
            }
        }
    while(cntEdge){
        temp = q.top();
        q.pop();
        if(find(temp.u) != find(temp.v)){
            merge(temp.u, temp.v);
            ans += temp.val;
        }
        cntEdge--;
    } // 这里在求总边权，不用管
    cout<<ans<<endl;

    return 0;
}

时间复杂度：\(O(E\log E)\)

[模板] Kruskal 求最小生成树

原文：https://www.cnblogs.com/Foggy-Forest/p/12970301.html