思路与算法

对完整欧式图做Prim得到最小生成树T和总长L，并计算树上任意两点路径中的最大边M(u,v)。若把(u,v)设为免费，最小应付总长为L-M(u,v)。枚举点对计算美味度和除以该值的最大比值。Prim每加入新点，可用其父亲已知路径最大值更新整行。

正确性说明

向T加入免费边形成一个环，删去原路径最大边即得代价L-M的生成树。反过来，任何含免费边的生成树删掉它后产生一个割，原路径上某条跨割边重量至多M，补回后总代价不小于原MST的L，故其应付代价不小于L-M。固定点对的美味度和为正，最小化分母即最大化该对比值，枚举所有对得到全局最优。

复杂度

完整图Prim O(N²)，路径最大值表更新与点对枚举各O(N²)，表及数组初始化O(N²)，总O(N²)时间、O(N²)空间。

易错点

坐标互不相同且N≥3，分母为正。欧氏距离与比值用long double；本题修订范围约定最优值远离两位舍入分界，最后统一保留两位，不能逐边提前取整。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> x(n), y(n), p(n), parent(n, -1);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i] >> p[i];
    vector<long double> d(n, 1e100L), path(n * n);
    vector<char> used(n);
    d[0] = 0;
    long double total = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!used[i] && (u < 0 || d[i] < d[u]))
                u = i;
        total += d[u];
        if (parent[u] >= 0)
            for (int v = 0; v < n; v++)
                if (used[v])
                    path[u * n + v] = path[v * n + u] = max(d[u], path[parent[u] * n + v]);
        used[u] = 1;
        for (int v = 0; v < n; v++)
            if (!used[v]) {
                long double dx = x[u] - x[v], dy = y[u] - y[v], dist = sqrtl(dx * dx + dy * dy);
                if (dist < d[v]) {
                    d[v] = dist;
                    parent[v] = u;
                }
            }
    }
    long double ans = 0;
    for (int u = 0; u < n; u++)
        for (int v = u + 1; v < n; v++)
            ans = max(ans, (p[u] + p[v]) / (total - path[u * n + v]));
    cout << fixed << setprecision(2) << ans << '\n';
}