• 1. 建边：两基站距离 ≤�≤l 时可连边，边权为欧氏距离。

  2. 目标：求使所有基站连通的最小生成树总边权。

  3. 特判：若无法全连通，输出 Impossible。

选择算法

• 最小生成树

思维之路

第一关:建边

• 最小生成树只可用于给出边的无向图

• 难点一：只给了点的座标，怎么算边？

  • 思维前置:勾股定理:

    • 我们用(�,�)(x,y)和(�1,�1)(x1,y1)这两个点为例，给(�,�)(x,y)命名为�A，给(�1,�1)(x1,y1)命名为�C。

    • 怎么算边？我们可以用勾股定理。

    • 勾股定理的定义:直角三角形里，两条直角边的平方加起来等于斜边的平方‌,公式：�2+�2=�2a2+b2=c2

    • 我们可以转换一下，推导得:�=�2+�2c=a2+b2​

    • 题目中采用平面直角坐标系，如图:

    

    • 推广一下：

      

    • �=�−�1a=x−x1,�=�−�b=y−y

    • 自己试试吧

  • 要注意哦：

    如果两座基站之间的距离不超过给定的整数�l，那么可以修建连接这两座基站的线路，线路长度为基站间的距离。

    还有：边长不能为负，记得abs!

• 代码片段:

  for(int i=1;i<=n;i++){
  	for(int j=i+1;j<=n;j++){
  		if(sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))<=l){
  			e[++m]={i,j,sqrt(abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y))};
  		}
  	}
  }
  

第二关:最小生成树

• 例题

• 详见流程图

• 代码片段:

    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
      int x=e[i].x,y=e[i].y;
      double z=e[i].z;
      if(find(x)!=find(y)){
        fa[find(x)]=find(y);
        ans+=z;
        if(++cnt==n-1)break;
      }
    }
    if(cnt==n-1)printf("%.2f\n",ans);
    else cout<<"Impossible";
  

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
	int x,y;
	double z;
}e[200200];
int n,m,fa[5050],cnt;
double ans;
struct at{
	double x,y;
}a[200200];
int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
}
bool cmp(edge p,edge q){
	return p.z<q.z;
}
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    double l;
    	cin>>n>>l;
    	ans=0,cnt=0,m=0;
    	for(int i=1;i<=n;i++){
    		cin>>a[i].x>>a[i].y;
    	}
	    for(int i=1;i<=n;i++){
	    	for(int j=i+1;j<=n;j++){
	    		if(sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))<=l)
	    			e[++m]={i,j,sqrt(abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y))};
	    	}
		}
	    sort(e+1,e+1+m,cmp);
	    for(int i=1;i<=n;i++)fa[i]=i;
	    for(int i=1;i<=m;i++){
	        int x=e[i].x,y=e[i].y;
			double z=e[i].z;
	        if(find(x)!=find(y)){
	            fa[find(x)]=find(y);
	            ans+=z;
	            if(++cnt==n-1)break;
	        }
	    }
	    if(cnt==n-1)printf("%.2f\n",ans);
	    else cout<<"Impossible";
    return 0;
}