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 ZjfAKIOI @ 2024-03-30 10:25:40

建议写kruscal

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,f[N],ans,bs,pd;
struct Edge{
    int u,v,w;
}e[N]; 
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
} 
bool cmp(Edge x,Edge y){
    return x.w<y.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++){
        int fv=find(e[i].v),fu=find(e[i].u);
        if(fv==fu) continue;
        f[fv]=fu;
        ans+=e[i].w;
        if(++bs==n-1){
            pd=1;
            break;  
        } 
    }
    if(!pd) cout<<"orz";
    else cout<<ans;
    return 0;
}

by __LePetitPrince__ @ 2024-03-30 10:36:33

扩展的时候如果 u 找不到怎么办 @spencer 你好像没处理

by __LePetitPrince__ @ 2024-03-30 10:37:17

btw 其实邻接表挺好用的，我一直用的邻接表，前向星看着特不舒服（

by __LePetitPrince__ @ 2024-03-30 10:39:24

@spencer 刚才讲的好像不大对（

你 dis 最开始是不是没赋极大值，为啥赋的是 w_i 这应该不对吧

by __LePetitPrince__ @ 2024-03-30 10:44:05

还有这个题是无向图阿，不知道你是不是搞成有向图了

by masonxiong @ 2024-03-30 10:59:29

首先，题目让建的是无向图

其次，不连通情况没判

而且，找距离最小的点应当用堆来优化，不优化可能时间复杂度不对

by __LePetitPrince__ @ 2024-03-30 11:06:06

@masonxiong 不联通判了吧，而且 O(n^2) 为啥不对

by masonxiong @ 2024-03-30 13:26:17

@LePetitPrince

你说得对，我的问题

by spencer @ 2024-03-30 15:08:29

@LePetitPrince dis[i]=w[i];那里是把与编号为1的点直接相连的点存入dis里

by spencer @ 2024-03-30 15:12:01

@LePetitPrince @masonxiong我搞成有向图了qwq，但改成无向图以后连样例都过不了了