社区讨论

刚学OI一秒钟 30pts 求问Prim

P3366【模板】最小生成树参与者 5已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@m3wn56fe
此快照首次捕获于
2024/11/25 14:22
去年
此快照最后确认于
2025/11/04 13:57
4 个月前
查看原帖
RT 30pts WA on #1-10
CPP
#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;
}

回复

10 条回复,欢迎继续交流。

正在加载回复...