Day 176-Q4 — 2026-10-12 | 最小比率全域木（Σa/Σb を最小にする全域木を、整数だけの Dinkelbach 法で既約分数として求める）

📋 コピーimport sys
from math import gcd


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    U = [int(x) - 1 for x in data[2:2 + 4 * m:4]]
    V = [int(x) - 1 for x in data[3:3 + 4 * m:4]]
    A = [int(x) for x in data[4:4 + 4 * m:4]]
    B = [int(x) for x in data[5:5 + 4 * m:4]]

    def kruskal(p, q):
        """辺の重み a_i*q - b_i*p（= q·(a_i - λ b_i)、λ = p/q）で最小全域木を作り、Σa と Σb を返す"""
        key = [a * q - b * p for a, b in zip(A, B)]
        order = sorted(range(m), key=key.__getitem__)
        par = list(range(n))
        sa = sb = 0
        need = n - 1
        for e in order:
            x, y = U[e], V[e]
            while par[x] != x:
                par[x] = par[par[x]]
                x = par[x]
            while par[y] != y:
                par[y] = par[par[y]]
                y = par[y]
            if x != y:
                par[x] = y
                sa += A[e]
                sb += B[e]
                need -= 1
                if need == 0:
                    break
        return sa, sb

    # Dinkelbach: λ_0 は任意の全域木の比。λ_{k+1} = (T_k の Σa)/(T_k の Σb)、T_k は a - λ_k b の最小全域木
    p, q = kruskal(0, 1)                     # λ = 0 のときの木（Σa 最小の木）から始める
    g = gcd(p, q)
    p, q = p // g, q // g
    while True:
        sa, sb = kruskal(p, q)
        if sa * q - sb * p >= 0:             # min Σ(a - λb) = 0 なら λ が最適
            break
        g = gcd(sa, sb)
        p, q = sa // g, sb // g
    print(f"{p}/{q}")


main()