社区讨论
刚学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 条回复,欢迎继续交流。
正在加载回复...