Kruskal算法:

C++ 代码

#include<algorithm>
#include<iostream>
using namespace std;

const int M = 100001, N = 1001;
int fa[N];
int n,m;
struct edge{
    int a,b,w;
}edges[M];

bool cmp(edge x,edge y){
    return x.w<y.w;
}

int find(int x){
    return x==fa[x] ? x : (fa[x]=find(fa[x])); 
}

int kruskal(){
    sort(edges, edges+m,cmp);
    int ans = 0;
    for(int i=1; i<=n; i++) fa[i] = i;
    for(int i=0; i<m; i++){
        int a = edges[i].a;
        int b = edges[i].b;
        if(find(a)!=find(b)){
            fa[find(a)] = find(b);
            ans += edges[i].w;
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a,b,w;
        cin>>a>>b>>w;
        edges[i] = {a,b,w};
    }
    cout<<kruskal();
    return 0;
}

Prim算法:

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1001;
int g[N][N];
int dist[N];
int st[N];
int n,m;

int prim(){
    int ans = 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;
        for(int j=1; j<=n; j++)
            if (!st[j])dist[j] = min(dist[j], g[t][j]);
        st[t] = 1;
        ans += dist[t];
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    memset(g, 0x3f, sizeof(g));
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b] = w;
        g[b][a] = w;
    }
    cout<<prim();
    return 0;
}