本文很长但是讲的很通俗了。题目链接洛谷链接https://www.luogu.com.cn/problem/P1522AcWing链接https://www.acwing.com/problem/content/1127/涉及知识1.图论与建图2.多源汇最短路和Floyed算法思路分析注意本题洛谷翻译和AcWing翻译有所不同洛谷要求新牧场直径最小值AcWing要求所有牧场最大直径的最小值。本文先按洛谷的翻译写最后再讲求AcWing要求的结果该如何做。第一部分厘清概念首先本题给出了很多概念我们先来逐一解析牧区一个点牧场很多个牧区组成一个牧场也就是点的连通块距离两点间的最短距离本题的距离是欧几里得距离这就是为什么本题底层逻辑上还是需要用最短路算法的原因直径牧场中最远的两个牧区的距离第二部分建图与预处理在正式求解之前我们需要思考如何建图。本题我们可以根据给定的领接矩阵若领接矩阵中G [ i ] [ j ] G[i][j]G[i][j]的值为 1那么就根据给定坐标求点i ii到j jj的距离 如果值为 0 则按照 Floyed 算法的规则赋值为 0 或正无穷。由于本题其后都需要使用“距离”我们先跑一遍 Floyed 算法求出数组d i s [ i ] [ j ] dis[i][j]dis[i][j]记录任意两点间的最短路即本题的距离。然后我们进一步思考新牧场的直径可能是怎样构成的我们连接的两点i ii和j jj是未连通的两点也就是说在连接时i ii和j jj应当分属两个不同的连通块A AA和B BB那么新牧场直径就有可能有三种情况情况一连通块A AA的直径即经过A AA内某一点的最远距离可能不经过点i ii情况二连通块B BB的直径即经过B BB内某一点的最远距离可能不经过点j jj情况三经过点i ii的最远距离 经过点j jj的最远距离 点i ii和 点j jj之间的路径长度注意到这三种情况都与从某一点出发的最远距离息息相关所以我们在跑完 Floyed 后用一个数组m a x d maxdmaxd来记录每一点的最远路径。第三部分结果的求解对于洛谷的翻译如果是要求解新牧场的直径的最小值我们只需要保证连接两点i ii和j jj时m a x d [ i ] m a x d [ j ] maxd[i]maxd[j]maxd[i]maxd[j]i ii和j jj的距离之和最小即可因为原有牧场的直径已经是固定的这个跨牧场的直径即上文的情况三是要大于等于所有原牧场的直径的最大值的否则无法构成直径。这也是本题最绕的地方。举个例子比如情况一的直径是 33情况二的直径是 44情况三我们求出最小是 44.5那么情况一和二无法构成直径而情况三我们已经求的是最小值也就求出了直径的最小值。而如果情况一的直径是 33情况二的直径是 44情况三求出来是 40那情况三就不可能成为直径直径的最小值为44。如果我们故意“施魔法”让情况三的数超过 33 和 44则又不满足对最小值的要求了。开个玩笑但就是这么个道理综上我们可以发现我们只需要保证先求情况三的最小值就一定可以在三者中找到直径的最小值。因此最后我们只需要分别把三种情况的直径求出来再取最大值就一定是直径的最小值了。对于 AcWing 的翻译求的是所有牧场的直径的最小值唯一的区别在于处理洛谷的翻译的题目我们是分了两种情况再连通块A AA和B BB中求直径因为必须是新生成的牧场。没有这条限制后我们则不需要在代码中特判当前点是否属于两个连通块直接求所有点的最远距离m a x d [ i ] maxd[i]maxd[i]再与m a x d [ i ] m a x d [ j ] maxd[i]maxd[j]maxd[i]maxd[j]i ii和j jj的距离之和取最大值即可。与网上其他做法相比本做法最大的优点在于不需要使用并查集等数据结构思路更为精练代码更为简洁可迁移性也很强。笔者水平有限若有错误和不足敬请指出AC代码洛谷版#includeiostream#includecstdio#includecmathusingnamespacestd;constintN200;constdoubleINF1e20;typedefpairdouble,doublePII;intn;doubledis[N][N],maxd[N];charG[N][N];PII farm[N];doubleget_dist(PII x,PII y){doubledxx.first-y.first,dyx.second-y.second;returnsqrt(dx*dxdy*dy);}voidfloyed(){for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}}}return;}intmain(){cinn;for(inti1;in;i)cinfarm[i].firstfarm[i].second;for(inti1;in;i){for(intj1;jn;j)cinG[i][j];}for(inti1;in;i){for(intj1;jn;j){if(G[i][j]1)dis[i][j]get_dist(farm[i],farm[j]);elsedis[i][j]ij?0:INF;}}floyed();for(inti1;in;i){for(intj1;jn;j){if(dis[i][j]INF)maxd[i]max(maxd[i],dis[i][j]);}}//两点连成的最大直径的最小值doubleres1INF;inta0,b0;for(inti1;in;i){for(intj1;jn;j){if(dis[i][j]INF){if(res1maxd[i]get_dist(farm[i],farm[j])maxd[j]){res1maxd[i]get_dist(farm[i],farm[j])maxd[j];ai,bj;}}}}//在连通块A中doubleres20.0;for(inti1;in;i){//判断点i和点a是否连通如果连通则说明在同一连通块中//但是这里取的是maxd[i]所以不一定会经过点aif(dis[i][a]INF)res2max(res2,maxd[i]);}//在连通块B中doubleres30.0;for(inti1;in;i){//同上if(dis[i][b]INF)res3max(res3,maxd[i]);}printf(%.6lf,max(res1,max(res2,res3)));// cout endl res1 res2 res3;return0;}AcWing版将情况一和二合并直接求出所有点的m a x d [ i ] maxd[i]maxd[i]的最大值#includeiostream#includecstdio#includecmathusingnamespacestd;constintN200;constdoubleINF1e20;typedefpairdouble,doublePII;intn;doubledis[N][N],maxd[N];charG[N][N];PII farm[N];doubleget_dist(PII x,PII y){doubledxx.first-y.first,dyx.second-y.second;returnsqrt(dx*dxdy*dy);}voidfloyed(){for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}}}return;}intmain(){cinn;for(inti1;in;i)cinfarm[i].firstfarm[i].second;for(inti1;in;i){for(intj1;jn;j)cinG[i][j];}for(inti1;in;i){for(intj1;jn;j){if(G[i][j]1)dis[i][j]get_dist(farm[i],farm[j]);elsedis[i][j]ij?0:INF;}}floyed();for(inti1;in;i){for(intj1;jn;j){if(dis[i][j]INF)maxd[i]max(maxd[i],dis[i][j]);}}//两点连成的最大直径的最小值doubleres1INF;inta0,b0;for(inti1;in;i){for(intj1;jn;j){if(dis[i][j]INF){if(res1maxd[i]get_dist(farm[i],farm[j])maxd[j]){res1maxd[i]get_dist(farm[i],farm[j])maxd[j];ai,bj;}}}}doubleres20.0;for(inti1;in;i){res2max(res2,maxd[i]);}printf(%.6lf,max(res1,res2));// cout endl res1 res2 res3;return0;}