Day 177-Q4 — 2026-10-13 | 完全グラフの最適比率全域木（辺を並べずに O(N^2) の Prim を Dinkelbach 法で数回だけ回す）

📋 コピーimport sys
from math import hypot


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    X = [int(v) for v in data[1:1 + 3 * n:3]]
    Y = [int(v) for v in data[2:2 + 3 * n:3]]
    Z = [int(v) for v in data[3:3 + 3 * n:3]]
    if n == 1:
        print("0.0000000000")
        return
    # 完全グラフなので辺を並べず、行列の行をその場で作る
    C = [[abs(Z[i] - zj) for zj in Z] for i in range(n)]                       # 費用（高さの差）
    L = [[hypot(X[i] - xj, Y[i] - yj) for xj, yj in zip(X, Y)] for i in range(n)]  # 長さ
    INF = float('inf')

    def prim(lam):
        """重み C - lam*L の最小全域木を O(N^2) の Prim で求め、(Σ費用, Σ長さ) を返す"""
        key = [INF] * n
        par = [0] * n
        block = [0.0] * n          # 木に入った頂点は INF にして二度と選ばない
        key[0] = 0.0
        sc = sl = 0.0
        u = 0
        for _ in range(n - 1):
            block[u] = INF
            key[u] = INF
            Cu, Lu = C[u], L[u]
            row = [c - lam * l + b for c, l, b in zip(Cu, Lu, block)]
            par = [u if r < k else p for r, k, p in zip(row, key, par)]
            key = [r if r < k else k for r, k in zip(row, key)]
            m = min(key)
            v = key.index(m)
            p = par[v]
            sc += C[p][v]
            sl += L[p][v]
            u = v
        return sc, sl

    lam = 0.0
    for _ in range(100):                       # Dinkelbach（Newton 法）。実際は数回で止まる
        sc, sl = prim(lam)
        nl = sc / sl
        if nl >= lam - 1e-12 * max(1.0, lam) and _ > 0:
            lam = min(lam, nl)
            break
        lam = nl
    print(f"{lam:.10f}")


main()