哪里不对?
查看原帖
哪里不对?
228788
ChangYiMing楼主2020/11/4 21:35
#include <stdio.h>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;

int read(){
	int a1=0,k1=1;char c1=getchar();
	while(c1<'0'||c1>'9'){
		if(c1=='-')k1=-1;c1=getchar();
	}
	while(c1>='0'&&c1<='9'){
		a1=a1*10+c1-'0';
		c1=getchar();
	}
	return a1*k1;
}
inline void out1(ll n) {
	if(n < 0)
		putchar ('-') , n = -n;
	if(n > 9)
		out1(n / 10);
	putchar(n % 10 + '0');
}
inline void out(ll n){
	out1(n);printf("\n");
}
struct Node {
	int x,y;
}a[1005];
bool mp[1005][1005];
struct Edge {
	int u,v;
	double dis;
}edge[500005];
int fa[1005];
double ans;
double com(int x,int y){
	return 1.0*sqrt(1.0*(a[x].x-a[y].x)*(a[x].x-a[y].x)+1.0*(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
void swap(int &a,int &b){
	int t=a;
	a=b;
	b=a;
}
bool cmp(Edge x,Edge y){
	return x.dis<y.dis;
}
int find(int x){
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}

int/*signed*/ main(){
//	freopen("Building Roads S.in","r",stdin);
//	freopen("Building Roads S.out","w",stdout);
	int n=read(),m=read(),num=m,sum=m;
	for(int i=1;i<=n;++i){
		a[i].x=read();a[i].y=read();
	}
	for(int i=1;i<=n;++i)fa[i]=i;
	for(int i=1;i<=m;++i){
		edge[i].u=read();edge[i].v=read();
		if(edge[i].u>edge[i].v)swap(edge[i].u,edge[i].v);
		edge[i].dis=com(edge[i].u,edge[i].v);
		mp[edge[i].u][edge[i].v]=true;
	}
	for(int i=1;i<n;++i){
		for(int j=i+1;j<=n;++j){
			if(mp[i][j])continue;
			edge[++num].u=i;edge[num].v=j;
			edge[num].dis=com(i,j);
		}
	}
	sort(edge+m+1,edge+num+1,cmp);
	for(int i=1;i<=m;++i){
		int f1=find(edge[i].u),f2=find(edge[i].v);
		if(f1==f2)continue;
		fa[f2]=f1;
	}
	for(int i=m+1;i<=num;++i){
		int f1=find(edge[i].u),f2=find(edge[i].v);
		if(f1==f2)continue;
		fa[f2]=f1;sum++;
		ans+=edge[i].dis;
		if(sum==n-1)break;
	}
	printf("%.2lf\n",ans);
	return 0;
}


2020/11/4 21:35
加载中...