社区讨论

最小生成树求助

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...