欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

算法:最小生成树模板(Prim算法+Kruskal算法)

程序员文章站 2022-04-19 14:05:24
算法:最小生成树模板(Prim算法+Kruskal算法)板子题参见:https://www.luogu.com.cn/problem/P3366Prim算法#includeusing namespace std;struct Edge{ int to,val,nexty;}edge[400005];int head[5005],cnt;void add(int u,int v,int val){ cnt++; edge[cnt...

算法:最小生成树模板(Prim算法+Kruskal算法)

板子题参见:https://www.luogu.com.cn/problem/P3366

Prim算法

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int to,val,nexty;
}edge[400005];
int head[5005],cnt;
void add(int u,int v,int val){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].nexty=head[u];
    head[u]=cnt;
}
int dis[5005];bool vis[5005];
struct node{
    int dis,num;
    bool operator<(const node &a)const{
        return dis>a.dis;
    }
};
priority_queue<node> qu;
int n,m,a,b,c;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dis[1]=0;
    int cnt=0,sum=0;
    qu.push((node){0,1});
    while(!qu.empty()&&cnt<n){
        node tmp=qu.top();
        int u=tmp.num;
        int d=tmp.dis;
        qu.pop();
        if(vis[u]) continue;
        cnt++;
        sum+=d;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nexty){
            int v=edge[i].to;
            if(edge[i].val<dis[v]){
                dis[v]=edge[i].val;
                qu.push((node){dis[v],v});
            }
        }
    }
    if(cnt==n) cout<<sum;
    else cout<<"orz";
}

Kruskal算法

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Edge{
    int u,v,val;
}edge[200005];
bool cmp(Edge a,Edge b){
    return a.val<b.val;
}
int fa[5005];
int cnt=0,sum=0;
int find(int x){
    return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>edge[i].u>>edge[i].v>>edge[i].val;
    }
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=m;i++){
        int uu=find(edge[i].u);
        int vv=find(edge[i].v);
        if(uu==vv) continue;
        fa[uu]=vv;
        cnt++;
        sum+=edge[i].val;
        if(cnt==n-1) break;
    }
    cout<<sum;
}

本文地址:https://blog.csdn.net/hebtu_Kangweiqi/article/details/107216650