社区讨论
最小生成树求助
学术版参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lvdv9135
- 此快照首次捕获于
- 2024/04/24 21:44 2 年前
- 此快照最后确认于
- 2024/04/25 13:45 2 年前
rt,不知道哪错了,只有75分
https://www.luogu.com.cn/problem/P3366
CPP#include <bits/stdc++.h>
//#include <queue>
using namespace std;
int n,m;
const int maxn = 5e3 + 1;
const int maxm = 2e5 + 1;
const int inf = 2147483647;
struct edge{
int fr,to,w,nxt;
}e[maxm];
int head[maxn] = {}, dis[maxn] = {};
struct E{
int x,d;
};
bool operator > (const E & _x,const E & _y){ return _x.d > _y.d;}
priority_queue <E,vector<E>,greater<E> >q;
int cnt_edge = 0;
bool vis[maxn] = {};
void add_edge(int x,int y,int z){
e[++cnt_edge] = (edge){x,y,z,head[x]};
head[x] = cnt_edge;
return ;
}
int res = 0, cnt = 0;
void Prim(int s){
dis[s] = 0;
q.push((E){s,0});
while(q.size()){
if(cnt >= n)break;
int u = q.top().x; q.pop();
if(vis[u] == true) continue;
vis[u] = true;
++cnt; res += dis[u];
for(int i = head[u]; i != -1; i = e[i].nxt){
int v = e[i].to;
if(dis[v] > e[i].w){
dis[v] = e[i].w;
q.push((E){v,dis[v]});
}
}
}
return ;
}
int main(){
cin>>n>>m;
for(int i = 1; i <= n; ++i) head[i] = -1,dis[i] = inf;
for(int i = 1; i <= m; ++i){
int x,y,z;
cin>>x>>y>>z;
add_edge(x,y,z);
add_edge(y,x,z);
}
Prim(1);
if(cnt == n) cout<<res;
else cout<<"orz";
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...