RE70分求助
查看原帖
RE70分求助
229056
Wased楼主2020/11/19 16:19

代码如下:

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int f[209901],n,m,cnt,sum;
double ans;
struct bian{
	int f,t;
	double v;
}a[209901];
struct sbwyz{
	int x1,y1;
}njl[209901];
bool cmp(bian x,bian y){
	return x.v<y.v;
}
int find (int x){
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
double get_len(int x,int y){
	double t=sqrt((double)(njl[x].x1-njl[y].x1)*(njl[x].x1-njl[y].x1)+(double)(njl[x].y1-njl[y].y1)*(njl[x].y1-njl[y].y1));
	return t;
}
void add(int x,int y,double t){
	a[++cnt].f=x;
	a[cnt].t=y;
	a[cnt].v=t;
}
int main(){
	int tmp_x,tmp_y;
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=n;i++){
		cin>>njl[i].x1>>njl[i].y1;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			register double t=get_len(i,j);
			add(i,j,t);
		}
	}
	for(int i=1;i<=m;i++){
		cin>>tmp_x>>tmp_y;
		add(tmp_x,tmp_y,0.0);
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		int fx=find(a[i].f);
		int fy=find(a[i].t);
		if(fx!=fy){	
			f[fx]=fy;
			sum++;
			ans+=a[i].v;
		}
		if(sum==n-1) break; 
	}
	printf("%.2lf\n",ans);
	return 0;
}
2020/11/19 16:19
加载中...