Prim

• 从单一顶点开始
• 不断加入最小的边，且边的一个顶点在树中一个顶点不在

#include<bits/stdc++.h>

using namespace std;

typedef struct{
    int t,l,nxt;
}E;
E edge[1010110];
int head[101010];
int cnt;


int n,m;

void insert(int a,int b,int v){
    edge[++cnt].t=b;
    edge[cnt].l=v;
    edge[cnt].nxt=head[a];
    head[a]=cnt;
}


struct ty{
    int x,len;
    bool operator < (const ty &a) const {
        return len>a.len;
    }
};

int dis[101010],vis[101010];
priority_queue<ty>q;
int prim(){
    int ans=0;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    for(int i=head[1];i!=-1;i=edge[i].nxt){
        ty tmp;
        tmp.x=edge[i].t;
        tmp.len=edge[i].l;
        // dis[tmp.x]=tmp.len;
        q.push(tmp);
    }
    while(!q.empty()){
        ty tmp=q.top();
        q.pop();
        if(vis[tmp.x]) continue;
        vis[tmp.x]=1;
        ans+=tmp.len;
        for(int i=head[tmp.x];i!=-1;i=edge[i].nxt){
            if(vis[edge[i].t])continue;
            if(dis[edge[i].t]<=edge[i].l) continue;
            ty tmp;
            tmp.x=edge[i].t;
            tmp.len=edge[i].l;
            q.push(tmp);            
        }
    }
    return ans;
}
int main(){
    memset(head,-1,sizeof(head));
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a,b,v;
        cin >> a >> b >> v;
        insert(a,b,v);
        insert(b,a,v);
    }
    cout << prim() << endl;
    return 0;
}

Kruskal