形式化题目

给定 $n$ 个顶点、$m$ 条有向边的带权图 $G=(V,E)$，边权 $w_{i,j}$ 为实数。$c=(c_1,c_2,\dots,c_k)$ 是一个圈，当且仅当 $c_i \to c_{i+1}$（$1 \leqslant i < k$）与 $c_k \to c_1$ 的边都存在，且 $c_1,\dots,c_k$ 互不相同。

圈 $c$ 的平均权定义为

即圈上所有边权之和除以边数。求全图所有圈的平均权最小值 $\mu^*=\min_c \mu(c)$，输出保留 8 位小数。

样例：下图中只有两类圈（不计同一条圈的反向不存在，因为是有向图），展示它们的平均权：

graph LR
    n1["点 1"] -->|"5"| n2["点 2"]
    n2 -->|"5"| n3["点 3"]
    n3 -->|"5"| n1
    n2 -->|"3"| n4["点 4"]
    n4 -->|"3"| n1

取较小者，输出 $3.66666667$。观察重点：平均权不是总权——长圈总权更大但平均权可以更小，因此不能只找"最短"的圈。

正解

思路

朴素做法及其瓶颈。 最直接的想法是枚举所有圈再算平均权，圈的数量是指数级的。退一步，按长度枚举圈：对每个起点 $s$、每个长度 $j$ 各做一次"恰好 $j$ 条边"的最短路 DP，取 $\min_{s,j} F_s[j][s]/j$，复杂度 $O(n^2 m) = 9\times 10^{10}$，不可接受。瓶颈很明确："从哪个点出发"这个维度把整张 DP 表复制了 $n$ 份——需要一个不依赖固定起点的刻画。

关键观察：只需考虑闭合行走。 任何闭行走（起点终点相同）都能分解成若干个圈：总权等于各圈权之和、总长等于各圈长之和，因此闭行走的平均权是各圈平均权的加权平均，不可能小于其中最小者；反过来圈本身就是闭行走。所以

而 $\mu^*$ 一定由长度不超过 $n$ 的圈达到（圈上顶点互异），不必枚举任意长的行走。

Karp 递推表。 定义 $F[j][v]$ 为：恰好 $j$ 条边、以 $v$ 结尾的最小权行走的权值（起点任取）。它满足

起点任取相当于把 $F[0]$ 全体置 0，"从哪出发"被折叠进同一个表里：固定长度 $j$ 扫一遍所有边即可推进一行，$n+1$ 行共 $O(nm)$ 次松弛。

Karp 定理（min-max 见证分数公式）。

直观理解：$F[n][v]$ 与 $F[k][v]$ 都是"终于 $v$"的最优行走，两者权值之差除以长度差，得到的是"多走 $n-k$ 条边"这段的平均权；对固定 $v$ 取 $\max_k$ 会剔除掉前缀异常便宜的干扰项，再对 $v$ 取 $\min$ 挑出最优终点。

正确性草证（下界方向）：设 $P$ 是终于 $v$ 的最优 $n$-行走。若 $P$ 在第 $k<n$ 步时也经过 $v$，则前缀本身是候选行走，$F[k][v]$ 不大于前缀权，于是 $\frac{F[n][v]-F[k][v]}{n-k}$ 不小于 $P$ 后缀（一条闭行走）的平均权 $\geqslant \mu^*$；否则 $P$ 的前 $n$ 个落点互异落在 $n-1$ 个点里，必有重复——$P$ 含圈，把圈对应的 $r$ 条边删去得 $k=n-r$ 的候选行走，同一分式不小于该圈平均权 $\geqslant \mu^*$。因此每个 $v$ 的 $\max$ 都 $\geqslant \mu^*$。上界方向是 Karp 定理的构造部分：把每条边权减去 $\mu^*$ 后全图圈权非负、最小平均圈权为 0；对它的最优到达行走反复绕圈可拼出任意长的最优行走，取其前 $n$ 条边的终点 $v$，该点的所有 $\frac{F[n][v]-F[k][v]}{n-k}$ 都不超过归一后的 $0$，两方向合起来即得等式。

用样例走一遍这张表（$n=4$，行是 $j$，列是 $v$，单元格为 $F[j][v]$，不可达处不会出现在本例）：

例如 $F[2][1]=6$ 来自行走 $2 \to 4 \to 1$（权 $3+3$），$F[4][4]=14$ 来自 $2 \to 4 \to 1 \to 2 \to 4$（$3+3+5+3$）。有了表之后按公式对每个终点算 $\max_k$：

对四个 $\max$ 取 $\min$ 得 $11/3 \approx 3.66666667$，与样例一致；见证点是点 4、$k=1$，分子 $F[4][4]-F[1][4]=14-3=11$，分母 $n-k=3$。

实现细节：$F$ 表共 $(n+1)\times n$ 个整数，用 array('q') 紧凑存储（72 MB）；"不可达"用大哨兵 $10^{15}$，热循环里不做哨兵剪枝——哨兵加负权仍远大于任何真实路径权，永远不会冒充可达值；最后一步用整数分数四舍五入到 8 位小数（对齐 printf 的远离零取整），避免浮点误差在第 9 位上翻转答案。另一种同阶常见做法是二分平均值 + 判负环，需要约 50 轮全量松弛，常数约为本做法的 50 倍。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 15:30
# update_at: 2026-09-30 15:30

import sys
from array import array

INF = 10**15  # 不可达哨兵：真实路径权值和 |w| 合计至多 3×10^10，远小于此


def relax(n: int, edges: list[tuple[int, int, int | float]], is_int: bool) -> list[array]:
    """Karp 递推表 F[j][v]：恰好 j 条边、以 v 结尾的最小权行走（起点任取）。"""
    kind = "q" if is_int else "d"
    rows: list[array] = [array(kind, [0] * n)]  # F[0][v] = 0：空行走权为 0
    prev = rows[0]
    for _ in range(n):
        # 上一行是哨兵时不剪枝：哨兵 + 负权仍落在哨兵带内，永远不会冒充真实值
        cur = [INF] * n
        for u, v, w in edges:
            x = prev[u] + w
            if x < cur[v]:
                cur[v] = x
        prev = array(kind, cur)
        rows.append(prev)
    return rows


def pick_witness(rows: list[array], n: int) -> tuple[int, int]:
    """按 Karp 公式挑出最小平均值的见证对 (v, k)：min_v max_k (F[n][v]-F[k][v])/(n-k)。"""
    fn = rows[n]
    best = [x / n for x in fn]  # k=0 候选：F[0][v]=0，故为 F[n][v]/n
    best_k = [0] * n
    for k in range(1, n):
        row = rows[k]
        step = 1.0 / (n - k)
        for v in range(n):
            q = (fn[v] - row[v]) * step  # 两个候选分数间隔 ≥ 1/(d1·d2)，浮点比较不会误序
            if q > best[v]:
                best[v] = q
                best_k[v] = k
    v0 = min(range(n), key=best.__getitem__)  # 取不到 F[n][v] 的点 best 恒大，不会当选
    return v0, best_k[v0]


def round8(num: int, den: int) -> str:
    """把整数分数 num/den 四舍五入到 8 位小数（0.5 远离零取整，对齐 printf）。"""
    sign = "-" if num < 0 else ""
    scaled = (2 * abs(num) * 10**8 + den) // (2 * den)
    whole, frac = divmod(scaled, 10**8)
    return f"{sign}{whole}.{frac:08d}"


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n, m = int(next(it)), int(next(it))

    # 权值允许实数（样例 2 的 -2.9）；纯整数输入走精确整数运算，保证 8 位小数不被浮点误差带偏
    edges: list[tuple[int, int, int | float]] = []
    is_int = True
    for _ in range(m):
        u, v = int(next(it)) - 1, int(next(it)) - 1
        token = next(it)
        if b"." in token:
            is_int = False
            w: int | float = float(token)
        else:
            w = int(token)
        edges.append((u, v, w))

    rows = relax(n, edges, is_int)
    v0, k0 = pick_witness(rows, n)
    num = rows[n][v0] - rows[k0][v0]  # 见证分数的分子，整数输入下精确
    den = n - k0
    print(round8(num, den) if is_int else f"{num / den:.8f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:22
 * update_at: 2026-10-05 05:22
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 3005;   // 顶点数上限（n <= 3000）
const int MAXM = 10005;  // 边数上限（m <= 10^4）
const double INF = 1e18; // 不可达哨兵：真实行走权值和至多 3*10^10，远小于此

int n, m;
int eu[MAXM], ev[MAXM]; // 每条有向边的起点、终点（下标从 1 开始）
double ew[MAXM];        // 每条边的权值（题目允许实数，如样例 2 的 -2.9）

// Karp 递推表：F[j][v] = 恰好走 j 条边、以 v 结尾的最小权行走（起点任取）
double F[MAXN][MAXN];

// 逐行递推 F 表：F[0][v] = 0 相当于超级源点向所有点连 0 权边，起点维度被折叠
void karp_dp() {
    for (int v = 1; v <= n; ++v) F[0][v] = 0;
    for (int j = 1; j <= n; ++j) {
        for (int v = 1; v <= n; ++v) F[j][v] = INF;
        for (int e = 1; e <= m; ++e) {
            int u = eu[e], v = ev[e];
            if (F[j - 1][u] >= INF / 2) continue; // 上一行不可达，不参与松弛
            double x = F[j - 1][u] + ew[e];
            if (x < F[j][v]) F[j][v] = x;
        }
    }
}

// Karp 定理：mu* = min_v max_k (F[n][v] - F[k][v]) / (n - k)
// 分数扫描用 long double：分子至多 6*10^10，long double 的精度保证
// 两个候选分数（间隔至少 1/(d1*d2) >= 1.1*10^-7）的比较不会误序
long double karp_answer() {
    long double ans = 1e18L;
    for (int v = 1; v <= n; ++v) {
        if (F[n][v] >= INF / 2) continue; // 没有长度恰为 n 的行走到达 v，跳过
        long double best = -1e18L;
        for (int k = 0; k < n; ++k) {
            long double fn = F[n][v];
            long double fk = F[k][v];
            long double q = (fn - fk) / (n - k); // 候选分数；F[k][v]=INF 时极小，不会当选
            if (q > best) best = q;
        }
        if (best < ans) ans = best;
    }
    return ans;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int e = 1; e <= m; ++e) {
        scanf("%d %d %lf", &eu[e], &ev[e], &ew[e]);
    }
    karp_dp();
    long double ans = karp_answer();
    printf("%.8Lf\n", ans);
    return 0;
}

复杂度

• 时间复杂度：$\mathcal{O}(nm + n^2)$。递推 $n+1$ 行、每行扫 $m$ 条边，共约 $3\times 10^{7}$ 次松弛；公式扫描 $(n+1)\times n \approx 9\times 10^{6}$ 次浮点比较（两个候选分数间隔至少 $1/(d_1 d_2) \geqslant 1.1\times 10^{-7}$，远大于浮点误差，比较不会误序）。与 C++ 正解同阶；实测最大规模组（$n=3000$、$m=10^4$）约 $2.1\,$s，本地限时 $20\,$s 内通过，OJ 时限 $1000\,$ms 下按约定允许 Python TLE。
• 空间复杂度：$\mathcal{O}(n^2)$。$F$ 表 $(n+1)\times n$ 个 int64 共约 $72\,$MB，低于 $128\,$MB 限制。

总结

1. 平均权问题先换模型：闭行走可分解为圈，故 $\mu^*$ 等于所有闭行走的最小平均权——这让"恰好 $j$ 条边"的 DP 能覆盖全部候选，不必固定起点。
2. Karp 表 + min-max 公式：$O(nm)$ 递推出 $F[j][v]$（起点任取），再按 $\min_v \max_k \frac{F[n][v]-F[k][v]}{n-k}$ 扫一遍即得精确的 $\mu^*$，比"二分答案 + 判负环"少掉对数轮松弛。
3. 工程细节决定精度：哨兵带与真实值分离，热循环可以不加分支；答案是分母 $\leqslant n$ 的有理数，用整数四舍五入输出 8 位小数，天然免疫浮点误差。