刚学OI一秒钟 30pts 求问Prim

donk_666 @ 2024-11-25 14:20:54

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
int n,m,ans;
int a[5005][5005];
int d[5005];
int vis[5005];
int prim(){
    priority_queue<pair<int,int> >q;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    q.push(mp(0,1));
    int tot=0;
    while(q.size()!=0){
        int x=q.top().second,value=q.top().first;q.pop();
        if(vis[x]==1){
            continue;
        }
    //    cout<<x<<" ";
        vis[x]=1;tot++;ans+=-value;
    //    cout<<ans<<" "<<value<<endl;
        for(int i=1;i<=n;i++){
            if(i==x||a[x][i]==0){
                continue;
            }
            if(d[i]>a[x][i]){
                d[i]=a[x][i];
                q.push(mp(-d[i],i));
            }
        }
    }
    if(tot!=n){
        return -1;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        a[u][v]=w;a[v][u]=w;
    }
    if(prim()==-1){
        cout<<"orz";return 0;
    }
    cout<<ans;
}

by ImposterAnYu @ 2024-11-25 14:46:02

你是78吗，不写Kruskal写Prim

by microchip @ 2024-11-25 14:48:02

@_meant_tobe 评价是不如去学 boruvka

by consequence @ 2024-11-25 14:50:25

最大值太小，没判重边，prim（）可能没有返回值

by consequence @ 2024-11-25 14:50:37

@_meant_tobe

by hepp @ 2024-11-25 14:52:43

@_meant_tobe

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
#define mp make_pair
int n,m,ans;
int a[N][N];
int d[N],vis[N];
int prim(){
    priority_queue<pair<int,int> >q;
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push(mp(0,1));
    int tot=0;
    while(q.size()){
        int x=q.top().second,value=q.top().first;q.pop();
        if(vis[x]==1){
            continue;
        }
    //    cout<<x<<" ";
        vis[x]=1;tot++;ans+=-value;
    //    cout<<ans<<" "<<value<<endl;
        for(int i=1;i<=n;i++){
            if(i==x||a[x][i]==0){
                continue;
            }
            if(d[i]>a[x][i]){
                d[i]=a[x][i];
                q.push(mp(-d[i],i));
            }
        }
    }
    if(tot!=n){
        return -1;
    }
    return 0;
}
void add(int &x,int y){
    if(!x) x=y;
    else x=min(x,y);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        add(a[u][v],w);
        add(a[v][u],w);
    }
    if(prim()==-1){
        cout<<"orz";return 0;
    }
    cout<<ans;
}

改好了,问题就是上面说的

by hepp @ 2024-11-25 14:53:06

蓝勾怎么这样子

by donk_666 @ 2024-11-25 14:57:51

@hepp @consequence thx

by ImposterAnYu @ 2024-11-25 15:00:33

@hepp 他头像和主页是曲奇饼干被人偷吃导致的，实力是太摆了导致的

by donk_666 @ 2024-11-25 15:01:14

@hepp

蓝钩是色诱CCF来的哈（光逃

by consequence @ 2024-11-25 15:04:09

@_meant_tobe 插一嘴，用邻接矩阵建图导致优先队列相当于没有优化，因为遍历一遍就 n^2 了。