蒟蒻求助这道题,卡了50pts
查看原帖
蒟蒻求助这道题,卡了50pts
308927
黄毛鸭子楼主2020/11/3 21:20

代码:

#include<bits/stdc++.h>
#define double long double
using namespace std;
struct node{
	double x,y;
	inline void read()
	{
		cin>>x>>y;
	}
}a[20009];
int f[20009],p[2009][2009];
struct E{
	int u,v;
	double w;
}e[20009];
int et;
inline double dis(int X,int Y)
{
	return (double)(sqrt((a[X].x-a[Y].x)*(a[X].x-a[Y].x)+(a[X].y-a[Y].y)*(a[X].y-a[Y].y)));
}
inline bool cmp(E x,E y)
{
	return x.w<y.w;
}
inline int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		a[i].read();
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		p[u][v]=p[v][u]=1;
		e[++et].u=u;
		e[et].v=v;
		e[et].w=0;
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(!p[i][j]) e[++et].u=i,e[et].v=j,e[et].w=dis(i,j);
		}
	int tops=0;
	double ans=0;
	sort(e+1,e+et+1,cmp);
	for(int i=1;i<=et;i++)
	{
		int tx=find(e[i].u),ty=find(e[i].v);
		if(tx!=ty)
		{
			f[tx]=ty;
			ans+=e[i].w;
			if(++tops>=n-1) break;
		}
	}
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}

谁能帮帮忙

2020/11/3 21:20
加载中...