最小生成树的模板题

解法一：prim算法

prim算法的原理
直接上y总的prim模板

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=110;

int g[N][N];
int n,m,fund;
int dist[N];
int st[N];

int prim(){
    
    int res=0;
    memset(dist,0x3f,sizeof dist);
    
    dist[1]=0;
    for(int i=0;i<n;++i){
        int t=-1;
        for(int j=1;j<=n;++j)
            if(!st[j]&&(t==-1||dist[j]<dist[t]))
                t=j;
        
        st[t]=1;
        if(i)
            res+=dist[t];
        for(int j=1;j<=n;++j) dist[j]=min(dist[j],g[t][j]);
    }
    
    return res;
}
int main(){
    cin>>fund>>m>>n;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    
    if(prim()>fund){
        cout<<"No";
    }else{
        cout<<"Yes";
    }
    return 0;
}

解法二： kruskal算法（克鲁斯卡尔算法）

kruskal原理 直接上模板

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=10010;

struct edge{
    int a,b,w;
    bool operator<(const edge& W)const{
        return w<W.w;
    }
}edges[N];

int ancient[N];

int find(int x){   //并查集相关：寻找祖宗节点
    if(ancient[x]!=x)
        ancient[x]=find(ancient[x]);
    return ancient[x];
}

int main(){
    
    int n,m,fund;
    cin>>fund>>m>>n;
    
    for(int i=0;i<m;++i){
        int a,b,c;
        
        cin>>a>>b>>c;
        edges[i]={a,b,c};
    }
    
    for(int i=1;i<=n;++i){
        ancient[i]=i;
    }
    
    sort(edges,edges+m);
    
    int amt=0;
    for(int i=0;i<m;++i){
        
        int a=edges[i].a,b=edges[i].b,c=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b){
            ancient[a]=b;
            amt+=c;
        }
    }
    if(amt>fund)
        cout<<"No";
    else
        cout<<"Yes";
    
    return 0;
    
}