题目传送门

Description

给定  个点，坐标分别为  ，定义两点距离为 ，若其小于  则可以连边。问是否可以选出  条满足条件的边，使所有点联通，并求出所有情况的最小值，否则输出 。

Solution

一道板子题。显然可以先把每两个点之间的距离求出来，排序后放到自定义结构体里面，用  和并查集跑一遍最小生成树，如果当前长度大于了   直接   ，最后检查一下  是否等于   即可。

时间复杂度          空间复杂度 

AC Code

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN=510;
constexpr int MAXL=110;

int n;
double l;
struct Edge{
	int u,v;
	double w;
	void make(int a,int b,int x1,int y1,int x2,int y2)
	{
		u=a,v=b;
		w=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
		return;
	}
}e[MAXN*MAXN]; int tot=0;
struct Point{
	int x,y;
	void make(int a,int b){x=a,y=b;return;}
}p[MAXN];

bool cmp(Edge pp,Edge qq){ return pp.w<qq.w; }

int f[MAXN];

int find(int s){ return f[s]==s?s:f[s]=find(f[s]); }
void merge(int u,int v)
{
	int fu=find(u),fv=find(v);
	f[fu]=fv;
	return;
}

signed main()
{
	//ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	scanf("%d%lf",&n,&l);
	for(int i=1,x,y;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		p[i].make(x,y);
		f[i]=i;
	}
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) e[++tot].make(i,j,p[i].x,p[i].y,p[j].x,p[j].y);
	sort(e+1,e+tot+1,cmp);
	int cnt=0;
	double ans=0;
	/*Kruskal*/for(int i=1;i<=tot;i++)
	{
		int u=e[i].u,v=e[i].v;
		double w=e[i].w;
		if(w>l) break;
		if(find(u)!=find(v))
		{
			merge(u,v);
			cnt++; ans+=w;
		}
	}
	if(cnt==n-1) printf("%.2lf",ans);
	else printf("Impossible");
	return 0;
}