prim保龄求调，样例可过，悬关！

spencer @ 2024-03-30 10:24:27

//prim

#include<bits/stdc++.h>
using namespace std;

const int N=5e3+50,M=2e5+50,inf=0x3f3f3f3f;
int a[M],nt[M],tot,h[M],w[M],n,m,vis[M],in[N],de[N],dis[N],ans=0;

void add(int x,int y,int z){
    a[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
    w[tot]=z;
    de[x]++,de[y]++;
}

int main(){
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
    }
    for(int i=1;i<=n;i++){
        if(de[i]==0){
            cout<<"orz";
            return 0;
        }
    }//判定不连通
    in[1]=1;
    for(int i=h[1];i;i=nt[i]){
        dis[i]=w[i];
    }
    for(int i=1;i<n;i++){
        int mind=inf,u=0;
        for(int j=1;j<=n;j++){
            if(dis[j]!=0&&dis[j]<mind)mind=dis[j],u=j;
        }//选择离集合距离最小的点
        ans+=mind;
        in[u]=1,dis[u]=0;//将u加入集合中
        for(int i=h[u];i;i=nt[i]){
            dis[i]=min(dis[i],w[i]);//更新dis
        }
    }
    cout<<ans;

    return 0;
}

by spencer @ 2024-03-30 15:14:48

@masonxiong 现在代码是这样的：

//prim

#include<bits/stdc++.h>
using namespace std;

const int N=5e3+50,M=2e5+50,inf=0x3f3f3f3f;
int a[M],nt[M],tot,h[M],w[M],n,m,vis[M],in[N],de[N],dis[N],ans=0;

void add(int x,int y,int z){
    a[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
    w[tot]=z;
    de[x]++;
}

int main(){
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=n;i++){
        if(de[i]==0){
            cout<<"orz";
            return 0;
        }
    }//判定不连通
    in[1]=1;
    for(int i=h[1];i;i=nt[i]){
        dis[i]=w[i];
    }
    for(int i=1;i<n;i++){
        int mind=inf,u=0;
        for(int j=1;j<=n;j++){
            if(dis[j]!=0&&dis[j]<mind)mind=dis[j],u=j;
        }//选择离集合距离最小的点
        if(mind==inf)break;
        ans+=mind;
        in[u]=1,dis[u]=0;//将u加入集合中
        for(int i=h[u];i;i=nt[i]){
            dis[i]=min(dis[i],w[i]);//更新dis
        }
    }
    cout<<ans;

    return 0;
}

by spencer @ 2024-03-30 16:37:26

@masonxiong 我又改了一下，49pts

//prim

#include<bits/stdc++.h>
using namespace std;

const int N=5e3+50,M=2e5+50,inf=0x3f3f3f3f;
int a[M],nt[M],tot,h[M],w[M],n,m,vis[M],in[N],de[N],dis[N],ans=0;

void add(int x,int y,int z){
    a[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
    w[tot]=z;
    de[x]++;
}

int main(){
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=n;i++){
        if(de[i]==0){
            cout<<"orz";
            return 0;
        }
    }//判定不连通
    in[1]=1;
    memset(dis,0x3f,sizeof dis);
    for(int i=h[1];i;i=nt[i]){
        dis[a[i]]=w[i];
    }
    dis[1]=0;
    for(int i=1;i<n;i++){
        int mind=inf,u=0;
        for(int j=1;j<=n;j++){
            if(dis[j]<mind&&dis[j]!=0)mind=dis[j],u=j;
        }//选择离集合距离最小的点
    /*  
        cout<<u<<'|';
        for(int j=1;j<=n;j++)cout<<dis[j]<<' ';
        cout<<'\n';
    */  

        if(mind==inf)break;
        ans+=mind;
        in[u]=1,dis[u]=0;//将u加入集合中
        for(int i=h[u];i;i=nt[i]){
            if(in[a[i]]==0) dis[a[i]]=min(dis[a[i]],w[i]);//更新dis
        }
    }
    cout<<ans;

    return 0;
}

by spencer @ 2024-03-30 16:43:28

但为什么会re啊？

by spencer @ 2024-03-30 16:54:34

re问题已解决，但有三个点wa了qwq

//prim

#include<bits/stdc++.h>
using namespace std;

const int N=5e3+50,M=5e5+50,inf=0x3f3f3f3f;
int a[M],nt[M],tot,h[M],w[M],n,m,vis[M],in[N],de[N],dis[N],ans=0;

void add(int x,int y,int z){
    a[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
    w[tot]=z;
    de[x]++;
}

int main(){
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=n;i++){
        if(de[i]==0){
            cout<<"orz";
            return 0;
        }
    }//判定不连通
    in[1]=1;
    memset(dis,0x3f,sizeof dis);
    for(int i=h[1];i;i=nt[i]){
        dis[a[i]]=w[i];
    }
    dis[1]=0;
    for(int i=1;i<n;i++){
        int mind=inf,u=0;
        for(int j=1;j<=n;j++){
            if(dis[j]<mind&&dis[j]!=0)mind=dis[j],u=j;
        }//选择离集合距离最小的点
    /*  
        cout<<u<<'|';
        for(int j=1;j<=n;j++)cout<<dis[j]<<' ';
        cout<<'\n';
    */  

        if(mind==inf)break;
        ans+=mind;
        in[u]=1,dis[u]=0;//将u加入集合中
        for(int i=h[u];i;i=nt[i]){
            if(in[a[i]]==0) dis[a[i]]=min(dis[a[i]],w[i]);//更新dis
        }
    }
    cout<<ans;

    return 0;
}

by spencer @ 2024-03-30 18:43:19

ac了，此贴结，orz