思路与算法

设f_k(v)为任意顶点出发，恰走k条边到v的最小权和，f_0全部为0。Karp公式为min_v max_{0≤k<n}(f_n(v)-f_k(v))/(n-k)。先滚动计算f_n，再从f_0重算一遍，逐层聚合比率，避免保存n²个实数。

正确性说明

恰长游走DP按最后一条边分解完整求出f_k。Karp最小平均圈定理将长度n的游走与所有较短前缀比较，最大比率排除有限非循环尾段，随后对终点取小得到全图最小圈均值。f_0全0相当于零费用超级源，可覆盖任意起点；第二遍重算与保存全表的公式完全相同。

复杂度

两遍DP及比率聚合O(nm+n²)，初始化O(n+m)，空间O(n+m)。n=3000时不分配约72MiB的double全表，以满足原64MiB限制。

易错点

边权可为负及小数，使用long double，中间有限性单独判断。不能把最小边或普通最短路当作最小平均圈。题目保证存在圈；最终固定8位小数，极小的数规范为0避免负零。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using D = long double;
struct E {
    int u, v;
    D w;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto &x : e) {
        cin >> x.u >> x.v >> x.w;
        --x.u;
        --x.v;
    }
    const D INF = 1e100L;
    vector<D> a(n, 0), b(n), fn, ratio(n, -INF);
    for (int k = 1; k <= n; k++) {
        fill(b.begin(), b.end(), INF);
        for (auto x : e)
            if (a[x.u] < INF / 2)
                b[x.v] = min(b[x.v], a[x.u] + x.w);
        a.swap(b);
    }
    fn = a;
    fill(a.begin(), a.end(), 0);
    for (int k = 0; k < n; k++) {
        for (int v = 0; v < n; v++)
            if (fn[v] < INF / 2 && a[v] < INF / 2)
                ratio[v] = max(ratio[v], (fn[v] - a[v]) / (n - k));
        fill(b.begin(), b.end(), INF);
        for (auto x : e)
            if (a[x.u] < INF / 2)
                b[x.v] = min(b[x.v], a[x.u] + x.w);
        a.swap(b);
    }
    D z = INF;
    for (int v = 0; v < n; v++)
        if (fn[v] < INF / 2)
            z = min(z, ratio[v]);
    if (fabsl(z) < 0.0000000001L)
        z = 0;
    cout << fixed << setprecision(8) << z << '\n';
}