可以不用最小生成树吗/只有10pts
查看原帖
可以不用最小生成树吗/只有10pts
1364351
rainy_morning楼主2024/12/28 09:10
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
long n,m,ans;
long g[N][N],a[N];
bool flag[N];
struct edge
{
	long x,y;
}e[N];


int main()
{
	cin>>n>>m;
	memset(g,0x3f,sizeof(g));
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		cin>>e[i].x>>e[i].y;
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
			g[i][j]=abs(e[i].x-e[j].x)+abs(e[i].y-e[j].y);
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i]=min(a[i],g[i][j]);
		}
	}
	
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u][v]=g[v][u]=1;
		flag[u]=flag[v]=1;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(flag[i]==0)
		{
			ans+=a[i];
		}
	}
	float anss=ans*1.000;
	printf("%.2f",anss);
}
2024/12/28 09:10
加载中...