prim堆优化炸了
查看原帖
prim堆优化炸了
420505
A_sh楼主2021/9/26 15:20

我的prim堆优化炸了三个点;

然鹅kruscal好好的;

acwing上交了一遍也是三个点炸;

貌似是连通图输出了orz;

但是找不到错误,求助;

贴码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f
const int N=1010,M=114514;

priority_queue< pair<int,int> > q;
int ans,tot;
int d[N],h[N],e[M],ne[M],v[M];
bool vis[M];
int m,n;

void add(int x,int y,int z){
	v[++tot]=y,e[tot]=z,ne[tot]=h[x],h[x]=tot;
}
inline void prim(){
	q.push(make_pair(0,1));
	int cnt=0,sum=0;
	while(q.size()){
		int x=q.top().second,dst=q.top().first;
		q.pop();
		if(vis[x])continue;//寻找更新点 
		vis[x]=1;
		sum-=dst;
		cnt++;
		for(int i=h[x];i;i=ne[i]){//-1
			if(!vis[v[i]]){
				q.push(make_pair(-e[i],v[i]));
			}
		}
	}
	if(cnt==n)printf("%lld",sum);
	else printf("orz"); 
}
inline int qr(){
	int res=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
signed main(){
	n=qr();m=qr();
	for(int i=1;i<=m;i++){
		int x=qr(),y=qr(),z=qr();
		add(x,y,z);
		add(y,x,z);
	}
	prim();
	return 0;
}
2021/9/26 15:20
加载中...