（模板）最小生成树

—————————————————————————————————————————————————— —————————————————————前排护眼——————————————————————— ——————————————————————————————————————————————————

1.Kruskal   O(ElogE)

//E为边数

//并查集，将边从大到小排序，另取一无边同结点图，遍历边，如果边的两个结点为不同连通分量，则连接边

int n,s,ans=0,num=0,fa[10002],m=0;
struct edge{
    int x,y,w;
}dd[100002];

int find(int xx){
    if(fa[xx]==xx)return xx;
    return fa[xx]=find(fa[xx]);
}
bool cmp(edge a,edge b){
    if(a.w<b.w)return 1;
    return 0;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        fa[i]=i;
        for(int j=1;j<=n;j++){
            scanf("%d",&s);
            if(i<j){
                num++;
                dd[num].x=i;
                dd[num].y=j;
                dd[num].w=s;
            }
        }
    }
    sort(dd+1,dd+num+1,cmp);
    for(int i=1;i<=num;i++){
        if(find(dd[i].x)!=find(dd[i].y)){
            ans+=dd[i].w;
            fa[find(dd[i].x)]=dd[i].y;
            m++;
            if(m==n-1)break;
        }
    }
    cout<<ans<<endl;
}

2.Prim   O(n^2)

//所有结点为白色，将结点1染蓝，将连接蓝-白结点的最短边入树并将白结点染蓝，重复n-1次

int n,s,vis[10002],num=0,b,w,ans=0;
struct node{
    int x,y,w;
    bool operator<(node a)const{
        return w>a.w;
    }
};
vector<node>q[10002];
priority_queue<node>p;
int main(){
    cin>>n;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&s);
            if(i==j)continue;
            q[i].push_back({i,j,s});
            q[j].push_back({j,i,s});
        }
    }
    vis[1]=1;
    for(int i=0;i<q[1].size();i++){
        p.push(q[1][i]);
    }
    while(num<n-1){
        b=p.top().y; w=p.top().w; p.pop();
        if(vis[b])continue;
        vis[b]=1;
        ans+=w;
        num++;
        for(int i=0;i<q[b].size();i++){
            p.push(q[b][i]);
        }
    }
    cout<<ans<<endl;
}

（模板）最小生成树

原文：https://www.cnblogs.com/xiaozezz/p/11930648.html