30分求调,必关
查看原帖
30分求调,必关
1384542
tsr_2012楼主2025/8/2 09:47

A了三个点,其他全wa

#include<bits/stdc++.h>
#define MAXN 1009
using namespace std;
typedef long long ll;
ll f[MAXN];
ll a[MAXN][3];
ll n,m;
ll cnt;
bool vis[MAXN];
long double ans;
struct Node{
	ll u,v;
	long double w;
}dis[MAXN*MAXN];
bool cmp(Node a,Node b){
	return a.w<b.w;
}
ll find(ll i){
	if(f[i]==i)return f[i];
	return f[i]=find(f[i]);
}
void k(){
	sort(dis+1,dis+1+cnt,cmp);
	for(ll i=1;i<=cnt;i++)
	{
		ll u=find(dis[i].u);
		ll v=find(dis[i].v);
		if(u==v)
		{
			continue;
		}
		ans+=dis[i].w;
		f[u]=v;
	}
}
int main()
{
	freopen("P2872_2.in","r",stdin);
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i][1]>>a[i][2];
		f[i]=i;
	}
	for(ll i=1;i<=m;i++)
	{
		cnt++;
		ll u,v;
		cin>>u>>v;
		dis[i].u=u;
		dis[i].v=v;
		dis[i].w=0;
		vis[u]=1;
		vis[v]=1;
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			if(!vis[i]||!vis[j]){
				cnt++;
				dis[cnt].u=i;
				dis[cnt].v=j;
				dis[cnt].w=(long double)sqrt((a[i][1]-a[j][1])*(a[i][1]-a[j][1])+(a[i][2]-a[j][2])*(a[i][2]-a[j][2]));
			}
		}
	}
	k();
	cout<<fixed<<setprecision(2)<<ans;
}
2025/8/2 09:47
加载中...