本文共 1271 字，大约阅读时间需要 4 分钟。

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

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

Prim算法

#include
   
    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
    
      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
    
   

Kruskal算法

#include
   
    using namespace std;int n,m;struct Edge{       int u,v,val;}edge[200005];bool cmp(Edge a,Edge b){       return a.val
    
     >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<
    
   

转载地址：http://pcef.baihongyu.com/