思路与算法

先用Floyd求各原连通分量内所有点对最短距离。求每点离心率ecc[u]，即它到本分量最远点的最短距离，并求所有原分量最大直径D。枚举不同分量的u,v，新桥长为欧氏距离；候选结果是max(D,ecc[u]+distance(u,v)+ecc[v])，取最小。

正确性说明

只添加一条跨分量边，原分量内部的最短路不能因走出再沿同桥返回而变短。新连接两分量的跨块最短路必须恰过这条桥，最远长度是两侧离心率与桥长之和；其他分量原直径也仍存在。因此给定桥时该max恰为全图最大直径，枚举全部跨分量端点覆盖所有允许新边，取min正确。

复杂度

距离矩阵初始化O(N²)，Floyd O(N³)，离心率和跨块枚举O(N²)，总时间O(N³)，空间O(N²)。使用long double并以六位小数输出，数值特判以整微单位比较避免浮点比较边界。

易错点

不能忘记没有被合并的第三个大分量。不能只比较桥长，也不能把直线交点当新顶点。输入保证至少两个分量；补充规范不把已连通图的无穷候选误输出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long double> x(n), y(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
    const long double INF = 1e30;
    vector<vector<long double>> d(n, vector<long double>(n, INF));
    auto distance = [&](int i, int j) {
        return hypotl(x[i] - x[j], y[i] - y[j]);
    };
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < n; ++j)
            if (s[j] == '1')
                d[i][j] = distance(i, j);
        d[i][i] = 0;
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    vector<long double> ecc(n);
    long double old = 0, best = INF;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (d[i][j] < INF / 2)
                ecc[i] = max(ecc[i], d[i][j]);
    for (auto e : ecc)
        old = max(old, e);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (d[i][j] >= INF / 2)
                best = min(best, max(old, ecc[i] + distance(i, j) + ecc[j]));
    cout << fixed << setprecision(6) << best << '\n';
}