悬一堆关
  • 板块灌水区
  • 楼主Ljh421
  • 当前回复9
  • 已保存回复9
  • 发布时间2025/1/24 17:20
  • 上次更新2025/1/24 21:04:25
查看原帖
悬一堆关
972511
Ljh421楼主2025/1/24 17:20

我的代码还有救吗

测试点

#include<bits/stdc++.h>
using namespace std;
const int N=5000+10;
int n,nb,f[N];
double ans,mp[N][N];
struct node{
	int x,y;
}a[N];
struct node2{
	int x,ju;
}b[N];
bool cmp(node2 A,node2 B){
	return A.ju<B.ju;
}
int find(int x){
	if(f[x]==x){
		return x;
	}
	f[x]=find(f[x]);
	return f[x];
}
int main(){
	
	scanf("%d",&n);
	nb=n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i].x!=a[j].x&&a[i].y!=a[j].y){
				mp[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
				mp[j][i]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
			}else{
				mp[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
				mp[j][i]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
			}
		}
	}
	while(nb!=1){
	for(int i=1;i<=n;i++){
		int x,y;
		double sma=N;
		for(int j=1;j<=n;j++){
			if(i!=j){
				if(mp[i][j]<sma){
					x=i,y=j;
					sma=mp[i][j];
				}
			}
		}
		b[x].x=y;
		b[x].ju=sma;
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(b[i].ju!=N){
			if(b[b[i].x].x==b[i].x){
				nb--;
				f[b[i].x]=f[i];
				ans+=b[i].ju;
				b[i].ju=N;
				b[b[i].x].ju=N;
			}else{
				int x=find(i),y=find(b[i].x);
				if(x!=y){
					f[y]=f[x];
					nb--;
					ans+=b[i].ju;
					b[i].ju=N;
					b[b[i].x].ju=N;
				}else{
					double sma=b[i].ju;
					int j=i,smaj=i;
					while(f[j]!=i){
						j=f[j];
						if(b[j].ju<sma){
							sma=b[j].ju;
							smaj=j;
						}
					}
					if(smaj!=i){
						ans=ans-sma+b[i].ju;
						f[b[i].x]=f[i];
					}
				}
			}
		}
	}
	}
	printf("%.2lf",ans);
    
    return 0;
}
2025/1/24 17:20
加载中...