MLE爆了
  • 板块P1265 公路修建
  • 楼主mysb
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/23 08:15
  • 上次更新2025/1/23 10:58:38
查看原帖
MLE爆了
1271310
mysb楼主2025/1/23 08:15
为什么MLE????
数组小了又RE
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,s,m,qq,k,ans;
int l;
const int INF=0x3f3f3f3f3f3f3f3f,N=5e6;
struct node{
	int x,y;
	double z;
}tr[N];
struct mode{
	int x,y;
}w[N];
int f[N];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
	f[find(x)]=find(y);
}
bool cmp(node x,node y){
	return x.z<y.z;
}
int sum;
double ku(){
	int c=0;
	double sum=0;
	for(int i=1;i<=l;i++){
		if(find(tr[i].x)!=find(tr[i].y)){
			sum+=tr[i].z;
			c++;
			merge(tr[i].x,tr[i].y);
		}
		if(n-1==c)break;
	}
	return sum;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=n;i++){
		cin>>w[i].x>>w[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i<j){
			tr[++l].x=i;
			tr[l].y=j;
			tr[l].z=sqrt((w[i].x-w[j].x)*(w[i].x-w[j].x)+(w[i].y-w[j].y)*(w[i].y-w[j].y));	
			}
		}
	}
	sort(tr+1,tr+1+l,cmp);
	double x=ku();
	printf("%.2f",x);
	return 0;
}
2025/1/23 08:15
加载中...