[GESP202606 八级] 线网建设题解

思维之路

第一关:建边

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

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

  • 思维前置:勾股定理:

    • 我们用(x,y)(x,y)和(x1,y1)(x1,y1)这两个点为例，给(x,y)(x,y)命名为AA，给(x1,y1)(x1,y1)命名为CC。

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

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

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

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

    • 推广一下：

    • a=x−x1a=x−x1,b=y−yb=y−y

    • 自己试试吧

  • 要注意哦：

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

    还有：边长不能为负，记得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; }