形式化题目

给定一张 $N$ 个顶点的无向图，顶点 $i$ 有坐标 $(X_i, Y_i)$；直接相连的两点之间距离为欧氏距离 $|p_ip_j|$，两点间的距离定义为最短路径长度。图的各连通分量称为牧场，一个牧场的直径是其中任意两点距离的最大值。

已知图至少有两个连通分量，要求恰好添加一条连接两个不同连通分量的边，使得新牧场的直径最小。若两条路径只在几何上交叉而不共享顶点，不算连通。

以样例为例，两个牧场与候选新边如下（实线为已有路径，虚线为最优新边）：

graph LR
  subgraph P0["牧场 1"]
    A([A])
    B([B])
    C([C])
    D([D])
    E([E])
  end
  subgraph P1["牧场 2"]
    F([F])
    G([G])
    H([H])
  end
  A ---|5.000000| B
  B ---|5.000000| C
  B ---|5.000000| D
  B ---|7.071068| E
  C ---|5.000000| E
  D ---|5.000000| E
  F ---|7.071068| G
  G ---|5.000000| H
  C -.-|新边 5.000000| G

牧场 1 由 $\{A,B,C,D,E\}$ 组成，牧场 2 由 $\{F,G,H\}$ 组成，两牧场之间没有任何路径。牧场 1 的直径由 $A$ 到 $E$ 贡献：$A-B-E = 5+\sqrt{50}\approx 12.071068$；图中虚线 $C-G$ 就是使新牧场直径最小的那条新边。

正解

思路

最直接的做法是：先对原图跑一次 Floyd 求出所有点对的最短路，再枚举要加的那条新边，每枚举一条就把边加进图里重跑一次 Floyd，算出新直径后取最小。这个做法是"正确"的，但 $O(N^2)$ 次枚举各配一次 $O(N^3)$ 的 Floyd，总复杂度 $O(N^5)$，$N=150$ 时约 $7.6\times 10^{10}$ 次运算，根本跑不完。

问题是：重跑真的必要吗？新边连接的是两个连通分量，它只有两个端点，所以重跑所改动的最短路其实只有跨分量那一部分，而这一部分有闭式解。下面两条性质把它讲清楚。

先用一个记号：$R(i)=\max_{v\,\in\,C(i)} d(i,v)$，即 $i$ 到自己所在牧场内最远点的距离，记 $i$ 所在连通分量为 $C(i)$。

性质 1：加一条边不会让原牧场内部的最短路变短。 设新边为 $(a,b)$，$a$、$b$ 分属牧场 $C_a$、$C_b$。如果牧场 $C_a$ 里原来某个最短路的更短替代方案用到了新边，它就必须走出 $C_a$、再从新边回来；但新边是连接这两个分量的唯一一条边（否则它们本来就连通），一来一回要走两遍，边权为正，去掉这段反而更短，矛盾。于是各牧场自己的直径原样保留，其中最大值

是答案无法绕过的下界。

性质 2：跨分量的点对，路径形状是固定的。 加新边 $(a,b)$ 之后，对 $u\in C_a$、$v\in C_b$，任何一条 $u\to v$ 的路都必须经过 $(a,b)$，于是

固定 $(a,b)$ 时，这一式对 $u$、$v$ 的最坏取值就是各自取"自家最远的点"，因此由跨分量路径贡献的直径是

把两个来源合起来：加边 $(a,b)$ 后的新直径恰为 $\max\bigl(D,\; R(a)+|p_ap_b|+R(b)\bigr)$。于是只需要 $O(N^3)$ 一次 Floyd 求出 $d$，再算 $R(i)$，最后 $O(N^2)$ 枚举跨分量的 $(a,b)$：

用样例核对这个公式。每个点的 $R(i)$ 与逐对候选值如下：

$D=\max_i R(i)=12.071068$。再枚举跨牧场点对，前几小的候选是：

最小值出现在 C–G，$\max(12.071068,\,22.071068)=22.071068$，与样例输出一致。加边后新牧场的直径确实是 F 到 D：$F\!-\!G$（$\sqrt{50}$）、$G\!-\!C$（$5$）、$C$ 再走两条长度为 $5$ 的路到达 $D$，合计 $7.071068+5+10=22.071068$。

这里必须单独强调一点，它是本题最容易写错的地方：$\max$ 里的 $D$ 不能省。当两个牧场各自很小、彼此也很近，而别的牧场直径更大时，会有 $R(a)+|p_ap_b|+R(b)<D$；真实数据 travel7 就是这种情形：它的 $D=39796.392691$ 大于最小候选 $22693.893986$，答案只能取 $D=39796.392691$。

代码里的名字与上面公式的对应关系是：span 就是 $d$（inf 表示两个牧区分属不同牧场），far[i] 就是 $R(i)$，diameter 就是 $D$，bridge 就是 $\min_{d(a,b)=\infty} R(a)+|p_ap_b|+R(b)$，最后 max(diameter, bridge) 保留 6 位小数输出。

核心循环是 Floyd 的向量化写法：第 $k$ 轮先把第 $k$ 列整列取出来（这一轮里它不会被改写），再让每一行整体取出 $\min\bigl(d[i][j],\, d[i][k]+col[j]\bigr)$，d[i][k] 为 inf（不连通）的行直接跳过。边界上，$N=2$ 且两点无边时 $D=0$、候选只有 $|p_0p_1|$ 一个，公式照样成立；某个牧场只有孤立一点时它的 $R=0$，等价于"贴着这个点连过去"。

另外两个实现细节也值得说明：

• 邻接矩阵必须逐位读，不能当成整数 token。01000000 会被 Python 解析成整数 1000000，行首的 0 直接消失，全 0 行更是变成 $0$ 位都没有；数据里也确实有实心行（travel0.in 第 33 行是 30 个连续的 1）。代码用字节切片 row[j : j + 1] 精确取出第 $j$ 位。
• 距离要先开方再 Floyd。"用平方距离省掉开方"在这里是错的：边权要参与加法，$(x+y)^2\ne x^2+y^2$，改成平方距离会把样例算成 11.180340。所以只在建边时开方一次，Floyd 全程用真实距离，输出时格式化为 6 位小数。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 06:09
# update_at: 2026-09-30 06:09

import sys
from math import dist, inf


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    n = int(next(tokens))
    points = [(float(next(tokens)), float(next(tokens))) for _ in range(n)]
    # 邻接矩阵的每一行是一个长度为 n 的 01 串，逐位取出。
    edge = [
        [float(row[j : j + 1]) for j in range(n)]
        for row in (next(tokens) for _ in range(n))
    ]

    # 边权参与加法，所以这里必须用真实距离：先开好方，Floyd 只做加减比较。
    span: list[list[float]] = [[inf] * n for _ in range(n)]
    for k, row in enumerate(edge):
        span[k][k] = 0.0
        for i, flag in enumerate(row):
            if flag and i != k:                       # 只有真的连了边才需要算距离
                span[k][i] = dist(points[k], points[i])

    for k in range(n):                                # Floyd：第 k 轮只用第 k 列当跳板
        col = [row[k] for row in span]                # 本轮内该列不会被改写，先取出来
        for i in range(n):
            begin = col[i]
            if begin < inf:                           # inf 表示 i 到 k 不连通，整行不用扫
                span[i] = [x if x <= begin + y else begin + y for x, y in zip(span[i], col)]

    far = [max(value for value in row if value < inf) for row in span]  # 每个点到本牧场最远点的距离
    diameter = max(far)                               # 只加一条边，原直径消不掉，是答案的下界
    bridge = min(                                     # 枚举连接两个不同牧场的边 (i, j)
        far[i] + dist(points[i], points[j]) + far[j]
        for i in range(n)
        for j in range(n)
        if span[i][j] == inf                          # inf 恰好表示 i、j 不在同一个牧场
    )
    print(f"{max(diameter, bridge):.6f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:58
 * update_at: 2026-10-05 00:00
 */
// main.cpp：Floyd 全源最短路 + 枚举连接两个牧场的新边。
// 答案 = max(原最大直径 D, min_{a,b 跨牧场} R(a)+|p_a p_b|+R(b))，
// 其中 R(i) 是 i 到本牧场内最远点的最短距离。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 155;        // 牧区数上限
const double INF = 1e18;     // 表示两点不在同一个牧场

int n;                       // 牧区数
double x[MAXN], y[MAXN];     // 每个牧区的坐标
double d[MAXN][MAXN];        // d[i][j]：i 到 j 的最短距离，INF 表示不在同一牧场
double far[MAXN];            // far[i] = R(i)：i 到本牧场内最远点的距离

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &x[i], &y[i]);

    // 邻接矩阵必须逐个字符读：'1' 表示有边，边权就是两点间的欧氏距离。
    // 注意对角线 d[i][i] 必须置 0，否则 Floyd 后它会被自己绕一圈的路径填上。
    for (int i = 0; i < n; i++) {
        char row[MAXN + 5];
        scanf("%s", row);
        for (int j = 0; j < n; j++) {
            d[i][j] = INF;
            if (row[j] == '1')
                d[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
        }
        d[i][i] = 0;
    }

    // Floyd 求全源最短路。
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];

    // R(i)：i 到本牧场内最远点的距离（对角线为 0，一定可达）。
    double diameter = 0;     // D：所有牧场直径的最大值，是答案的下界，不能丢
    for (int i = 0; i < n; i++) {
        far[i] = 0;
        for (int j = 0; j < n; j++)
            if (d[i][j] < INF && d[i][j] > far[i])
                far[i] = d[i][j];
        if (far[i] > diameter)
            diameter = far[i];
    }

    // 枚举新边 (a, b)：a、b 必须分属两个牧场（d[a][b] == INF）。
    // 跨牧场点对的路径必经新边，新牧场直径 = max(D, R(a)+|p_a p_b|+R(b))。
    double bridge = INF;     // 所有候选新边中最小的 R(a)+|p_a p_b|+R(b)
    for (int a = 0; a < n; a++)
        for (int b = 0; b < n; b++)
            if (d[a][b] >= INF) {
                double len = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
                bridge = min(bridge, far[a] + len + far[b]);
            }

    printf("%.6f\n", max(diameter, bridge));
    return 0;
}

复杂度

• 时间复杂度：$O(N^3)$，Floyd 贡献全部主要开销；求 $R(i)$ 与枚举新边都是 $O(N^2)$。
• 空间复杂度：$O(N^2)$，用于存储最短路表与邻接矩阵。

总结

• 牧场 = 连通分量，牧区距离 = 分量内最短路，牧场直径 = 分量内最大点对距离。
• 加边不会改变原分量内部的最短路，所以原有最大直径 $D$ 是答案下界，必须用 max 保留。
• 跨分量点对的路径被新边唯一决定，最坏情况只取决于 $R(i)=$ “到本牧场最远点的距离”： $\text{answer}=\min_{a,b\text{ 跨分量}}\max\bigl(D,\,R(a)+|p_ap_b|+R(b)\bigr)$。
• 关键是把"枚举新边 + 重跑 Floyd"的 $O(N^5)$ 换成"一次 Floyd + $R$ 表"的 $O(N^3)$。
• 两个易错点：01 邻接矩阵要逐位读；距离要在建边时就开方，不能拿平方距离做 Floyd。