最小生成树

Cobalt · 2018-09-18 20:04:56 · 个人记录

洛谷 P3366 【模板】最小生成树

Kruskal:

#include<iostream> 
#include<algorithm>
using namespace std;
struct edge{
    int u,v,w;
    friend bool operator <(edge a,edge b){
        return a.w<b.w;
    }
};
edge e[200010];
int n,m,eCnt,ans,f[5010];
int getf(int x){
    if(f[x]==x)
        return x;
    return f[x]=getf(f[x]);
}
inline void merge(int x,int y){
    f[getf(x)]=getf(y);
}
inline void add(int u,int v,int w){
    edge t;
    t.u=u,t.v=v,t.w=w;
    e[++eCnt]=t;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        if(getf(e[i].u)!=getf(e[i].v)){
            ans+=e[i].w;
            merge(e[i].u,e[i].v);
        }
    }
    getf(1);
    for(int i=2;i<=n;i++)
        if(getf(i)!=f[1]){//无解的情况
            cout<<"orz";
            return 0;
        }
    cout<<ans;
    return 0;
}

Prim:

#include<iostream>
#include<queue>
#define N 5010
#define inf 99999999
using namespace std;
int a[N][N],dis[N],n,m,ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=inf;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(a[u][v]>w)//判断重边 
            a[u][v]=a[v][u]=w;
    }
    //初始化dis数组 
    for(int i=1;i<=n;i++)
        a[i][i]=0,dis[i]=inf;
    for(int i=1;i<=n;i++)
        dis[i]=a[1][i];
    for(int p=1;p<=n-1;p++){
        int vmin=inf,x;
        for(int i=1;i<=n;i++){
            if(dis[i]&&dis[i]<vmin){
            //这里需要dis[i]不为0 
                vmin=dis[i];
                x=i;
            }
        }
        ans+=dis[x];
        dis[x]=0;
        for(int i=1;i<=n;i++)
            if(dis[i]>a[x][i])
                dis[i]=a[x][i];//更新dis数组 
    }
    cout<<ans;
    return 0;
}