[GESP202606 八级] 线网建设题解

思维之路第一关:建边最小生成树只可用于给出边的无向图难点一只给了点的座标怎么算边思维前置:勾股定理:我们用(x,y)(x,y)和(x1,y1)(x1,y1)这两个点为例给(x,y)(x,y)命名为AA给(x1,y1)(x1,y1)命名为CC。怎么算边我们可以用勾股定理。勾股定理的定义:直角三角形里两条直角边的平方加起来等于斜边的平方‌,公式a2b2c2a2b2c2我们可以转换一下推导得:ca2b2ca2b2​题目中采用平面直角坐标系如图:推广一下ax−x1ax−x1,by−yby−y自己试试吧要注意哦如果两座基站之间的距离不超过给定的整数ll那么可以修建连接这两座基站的线路线路长度为基站间的距离。还有边长不能为负记得abs!代码片段:for(int i1;in;i){ for(int ji1;jn;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(e1,e1m,cmp); for(int i1;in;i)fa[i]i; for(int i1;im;i){ int xe[i].x,ye[i].y; double ze[i].z; if(find(x)!find(y)){ fa[find(x)]find(y); ansz; if(cntn-1)break; } } if(cntn-1)printf(%.2f\n,ans); else coutImpossible;代码实现#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.zq.z; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); double l; cinnl; ans0,cnt0,m0; for(int i1;in;i){ cina[i].xa[i].y; } for(int i1;in;i){ for(int ji1;jn;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(e1,e1m,cmp); for(int i1;in;i)fa[i]i; for(int i1;im;i){ int xe[i].x,ye[i].y; double ze[i].z; if(find(x)!find(y)){ fa[find(x)]find(y); ansz; if(cntn-1)break; } } if(cntn-1)printf(%.2f\n,ans); else coutImpossible; return 0; }