求助prim10分wa9个点
查看原帖
求助prim10分wa9个点
717599
dengjunhaodejia09楼主2022/12/30 16:22
#include<bits/stdc++.h>
using namespace std;
long long cnt,tot,head[100100],n,m;
struct oooo{
	long double qi;
	long long xx,yy;
}hhh[100100];
long double dis[100100],mst;
struct node{
	long long to,next;
	long double w;
}e[400100];
bool f[100100];
priority_queue<pair<long double, long long> > q;
inline void add(long long x,long long y,long double z){
	cnt++;
	e[cnt].to=y;
	e[cnt].w=z;
	e[cnt].next=head[x];
	head[x]=cnt;
}
long long s1[10000],s2[10000];
long double ojld(long long a1,long long b1){
	return sqrt((long double)(pow((s1[a1]-s1[b1]),2))+(long double)(pow((s2[a1]-s2[b1]),2)));
}

void chushihua(){
	for(long long i=1;i<=n;i++){
		for(long long j=i+1;j<=n;j++){
			long double g=ojld(i,j);
			if(g<hhh[i].qi){
				hhh[i].qi=g;
				hhh[i].xx=i;
				hhh[i].yy=j;
			}
			if(g<hhh[j].qi){
				hhh[j].qi=g;
				hhh[j].xx=i;
				hhh[j].yy=j;
			}
		}
	}
	for(long long i=1;i<=n;i++){
		if(hhh[i].xx!=-1 && hhh[i].yy!=-1){
			add(hhh[i].xx,hhh[i].yy,hhh[i].qi);
		}
	}
}


int main(){
	for(long long i=0;i<=100000;i++){
		hhh[i].xx=-1;
		hhh[i].yy=-1;
		hhh[i].qi=DBL_MAX;
		dis[i]=DBL_MAX;
	}
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>s1[i]>>s2[i];
	}	
	chushihua();
	dis[1]=0;
	f[1]=true;
	for(long long i=head[1];i!=0;i=e[i].next){
		if(f[e[i].to]){
			continue;
		}else{
			if(dis[e[i].to]>e[i].w){
				dis[e[i].to]=e[i].w;
			}
		}
	}
	for(int i=1;i<n;i++){
		long long weizhi=-1;
		double minn=DBL_MAX;
		for(long long i=1;i<=n;i++){
			if(minn>dis[i] && f[i]==false){
				minn=dis[i];
				weizhi=i;
			}
		}
		if(weizhi!=-1){
			mst+=minn;
			f[weizhi]=true;
			for(long long i=head[weizhi];i!=0;i=e[i].next){
				if(f[e[i].to]){
					continue;
				}else{
					if(dis[e[i].to]>e[i].w){
						dis[e[i].to]=e[i].w;
					}
				}
			}
		}
		
	}
	
	cout<<fixed<<setprecision(2)<<mst;
	
	return 0;
}
2022/12/30 16:22
加载中...