【玄关】40pts 求调
  • 板块P1433 吃奶酪
  • 楼主mysterys
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/7/3 10:51
  • 上次更新2024/7/3 11:10:59
查看原帖
【玄关】40pts 求调
659165
mysterys楼主2024/7/3 10:51
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
map<int,pair<int,int>>s;
struct edge{
	int x,y;
	double z;
}e[550];
int n,m,fa[35];
double ans=0.00;
inline double dis(int i,int j){
	return sqrt((s[i].first-s[j].first)*(s[i].first-s[j].first)+(s[i].second-s[j].second)*(s[i].second-s[j].second));
}
inline bool cmp(edge x,edge y){
	return x.z<y.z;
}
namespace T{
	void init(){
		for(int i=1;i<=n+2;i++) fa[i]=i;
	}	
	inline int find(int x){
		return (fa[x]==x?fa[x]:fa[x]=find(fa[x]));
	}
};
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cout.tie(nullptr);
	cin>>n;
	s[1]=make_pair(0,0);
	for(int i=1;i<=n;i++){
		int X,Y;
		cin>>X>>Y;
		s[i+1]=make_pair(X,Y);
	}
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=n+1;j++){
			if(i==j) continue;
			e[++m]=(edge){i,j,dis(i,j)};
			//e[++m]=(edge){j,i,dis(i,j)};
		}
	}
	stable_sort(e+1,e+m+1,cmp);
	int tot=0;
	T::init();
	for(int i=1;i<=m;i++){
		int r1=T::find(e[i].x),r2=T::find(e[i].y);
		if(r1!=r2){
			fa[r1]=r2;
			++tot;
			ans+=e[i].z;
		}
		//if(tot==n) break;
	}
	printf("%.2lf",ans);
	return 0;
}
2024/7/3 10:51
加载中...