当前位置： 移动技术网 > 移动技术>移动开发>Android > 算法：最小生成树模板（Prim算法+Kruskal算法）

算法：最小生成树模板（Prim算法+Kruskal算法）

2020年07月09日  | 移动技术网移动技术  | 我要评论

算法：最小生成树模板（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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网