形式化题目

给定 $L$ 个点、$P$ 条边的有向图。点 $v$ 有点权 $f_v$（乐趣值），边 $u \to v$ 有边权 $t(u,v)$（耗时）。找一个环 $C$（点与边交替、首尾相接，至少含一条边），最大化

输出最大比值，保留两位小数。数据保证至少存在一个环。

下面用样例图展示环的结构：每个点标 $f$ 值，每条边标 $t$ 值，加粗路线 $1 \to 2 \to 3 \to 5 \to 1$ 就是最优环。

graph LR
    A(("1<br>f=30")) -->|t=3| B(("2<br>f=10"))
    B -->|t=2| C(("3<br>f=10"))
    C -->|t=5| D(("4<br>f=5"))
    C -->|t=2| E(("5<br>f=10"))
    D -->|t=5| E
    E -->|t=3| A
    E -->|t=2| B
    style A fill:#ffe0b2
    style B fill:#ffe0b2
    style C fill:#ffe0b2
    style E fill:#ffe0b2

样例答案来自粗线环 $1 \to 2 \to 3 \to 5 \to 1$：分子 $f_1+f_2+f_3+f_5 = 30+10+10+10 = 60$，分母 $3+2+2+3 = 10$，比值 $60/10 = 6.00$。观察这张图可以发现一个关键结构：环上每个点恰好对应一条入边（点 $v$ 的入边就是环上指向它的那条边），点与边一一交替——这正是下一步把点权"挂"到边上的伏笔。

正解

思路

朴素做法及其瓶颈：把图中每个环都找出来，逐个算 $\sum f / \sum t$ 取最大。有向图简单环的数量是指数级的（$L \leqslant 1000$），根本枚举不完。瓶颈在于「环」没法线性枚举，必须把「找一个环」换成「回答一个能高效判定的问题」。

第一步：01 分数规划（分式转线性）。 设当前猜测比值 $mid$，问：存在环 $C$ 使 $F(C)/T(C) > mid$ 吗？其中 $F(C)$ 是环上点权和、$T(C)$ 是环上边权和。移项：

右边就是「把每条边的权改成 $mid \cdot t_e$、再把环上点权全部减掉后，环权和为负」。利用上面观察到的「环上点与入边一一对应」，把 $f_v$ 挂到 $v$ 的入边上——给每条边 $u \to v$ 定新权：

这样环 $C$ 的边权和恰好等于 $mid \cdot T(C) - F(C)$，于是

「找环」变成了「判负环」，后者是经典可解问题。

第二步：SPFA 判负环。 图不一定强连通，等效做法是从一个虚拟超级源点向所有点连 $0$ 边跑最短路——实现上就是 dis 全 $0$、所有点初始入队。用 cnt[v] 记录点 $v$ 的 dis 被成功松弛的次数：无负环时最短路至多经过 $n-1$ 条边，每点至多被松弛 $n-1$ 次；一旦 cnt[v] >= n，由抽屉原理必经过负环，立即返回有负环。

第三步：二分收敛。 $mid$ 越大，每条边权 $mid \cdot t_e - f_v$ 越大，负环从「有」单调变「无」，所以二分方向明确：

即：有负环说明答案比 $mid$ 大，抬 lo；无负环说明答案不超过 $mid$，压 hi。比值上界是 $1000/1 = 1000$（分子每点至多 $1000$、分母每边至少 $1$），下界 $0$。30 轮二分后区间长 $1000/2^{30} < 10^{-6}$，两位小数输出绰绰有余。最优比值由某个真实环取到，收敛后输出 hi 即答案。

代码

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
83
84/**
 * 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-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 观光旅游：01 分数规划 + SPFA 判负环
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

int L, P;
vector<ll> fun;      // fun[i]：景点 i 的乐趣值
vector<int> eu, ev, et;
vector<vector<int> > out_edges; // out_edges[u]：u 的出边编号，按输入顺序
vector<double> dis;
vector<int> relax;
vector<char> inq;

// 图（边权为 mid*t - f）中是否存在负环
bool has_neg_cycle(double mid) {
    // 超级源点连向所有点：dis 初始全 0，所有点一开始都在队列里
    dis.assign(L + 1, 0.0);
    relax.assign(L + 1, 0);
    inq.assign(L + 1, 1);
    vector<int> q;
    for (int i = 1; i <= L; i++) {
        q.push_back(i);
    }
    for (int qh = 0; qh < (int)q.size(); qh++) {
        int u = q[qh];
        inq[u] = 0;
        for (int t = 0; t < (int)out_edges[u].size(); t++) {
            int e = out_edges[u][t];
            int v = ev[e];
            double nd = dis[u] + (mid * et[e] - fun[v]); // 点权 f 记在边的终点上
            if (nd < dis[v]) {
                dis[v] = nd;
                relax[v]++;
                if (relax[v] >= L) { // 一个点被松弛 n 次 ⇒ 存在负环
                    return true;
                }
                if (!inq[v]) {
                    inq[v] = 1;
                    q.push_back(v);
                }
            }
        }
    }
    return false;
}

int main() {
    if (scanf("%d %d", &L, &P) != 2) {
        return 0;
    }
    fun.assign(L + 1, 0);
    for (int i = 1; i <= L; i++) {
        scanf("%lld", &fun[i]);
    }
    eu.assign(P, 0); ev.assign(P, 0); et.assign(P, 0);
    out_edges.assign(L + 1, vector<int>());
    for (int i = 0; i < P; i++) {
        scanf("%d %d %d", &eu[i], &ev[i], &et[i]);
        out_edges[eu[i]].push_back(i);
    }

    // 二分比值 mid：有负环 ⇔ 存在环的 Σf/Σt > mid
    double lo = 0.0, hi = 1000.0;
    for (int it = 0; it < 30; it++) {
        double mid = (lo + hi) / 2;
        if (has_neg_cycle(mid)) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    printf("%.2f\n", hi);
    return 0;
}

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#!/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-10-02 00:36
# update_at: 2026-10-02 00:36

import sys
from collections import deque


def has_neg_cycle(n: int, graph: list[list[tuple[int, int]]]) -> bool:
    """图（边权为 mid*t - f）中是否存在负环（SPFA 判负环）。"""
    cnt = [0] * (n + 1)               # cnt[v] = 点 v 被松弛的次数
    in_queue = [False] * (n + 1)
    dis = [0.0] * (n + 1)             # 超级源点连向所有点，dis 初始全 0
    queue = deque(range(1, n + 1))    # 超级源点入队等价于所有点初始就在队列里
    in_queue[1:] = [True] * n

    while queue:
        u = queue.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            nd = dis[u] + w
            if nd < dis[v]:
                dis[v] = nd
                cnt[v] += 1
                if cnt[v] >= n:       # 一个点被松弛 n 次 ⇒ 经过它存在负环
                    return True
                if not in_queue[v]:
                    in_queue[v] = True
                    queue.append(v)
    return False


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    L = next(data)  # 点数
    P = next(data)  # 边数

    fun = [0] + [next(data) for _ in range(L)]  # 点权：fun[i] = 景点的乐趣值

    # 邻接表：u -> [(v, time), ...]
    graph: list[list[tuple[int, int]]] = [[] for _ in range(L + 1)]
    for _ in range(P):
        a, b, t = next(data), next(data), next(data)
        graph[a].append((b, t))

    # 01分数规划：二分比值 mid，判是否存在环满足 Σ(mid*t - f) < 0，即环的 Σf/Σt > mid
    lo, hi = 0.0, 1000.0  # f,t 均 <= 1000，比值不超过 1000
    for _ in range(30):   # 30 次二分后区间长 < 1e-6，足够保留两位小数
        mid = (lo + hi) / 2
        # 点权 f 记在边的终点上：环的边权和 = mid·Σt - Σf(环上点)
        graph_adj = [[(v, mid * t - fun[v]) for v, t in adj] for u, adj in enumerate(graph)]
        if has_neg_cycle(L, graph_adj):  # 有负环 ⇒ 存在环的比值 > mid
            lo = mid   # 答案比 mid 大，抬高下界
        else:
            hi = mid   # 所有环的比值 <= mid，压低上界

    print(f'{hi:.2f}')  # 二分收敛到最大比值


if __name__ == "__main__":
    solve()

复杂度

• 时间：每轮 SPFA 最坏 $O(L \cdot P)$，二分 30 轮，总计 $O(30 \cdot L \cdot P) \approx 1.5 \times 10^8$（上界；实际 SPFA 表现远好于最坏情况，全部测试数据在 Python 下本地最大耗时 0.2s）。
• 空间：邻接表与每轮重建的带权边表均为 $O(L + P)$。

总结

• 本题模型是最优比率环：分式目标 $\max F(C)/T(C)$ 用 01 分数规划转成线性判定「新图是否有负环」，二分 + SPFA 解决。
• 三个实现关键点：
  1. 点权必须挂到边的终点（$w = mid \cdot t - f_v$），环上点与入边一一对应，环权和才恰好是 $mid \cdot T - F$；
  2. 二分方向：有负环 ⇒ 答案 $> mid$ ⇒ 抬 lo；
  3. 判负环用精确准则 cnt[v] >= n，且所有点初始入队——图不强连通，「总松弛次数超过常数倍 $n$」这类启发式早停会在无负环的大图上误判。
• 同一套套路适用于所有「最大化 分子量/分母量」的图上结构问题（最优比率生成树、最优比率路径等），差别只在分子分母挂在什么元素上、以及用什么算法判负权。

图示解析

01 分数规划的转化路线

从「枚举所有环」到「二分 + 判负环」的完整推导链：

graph TD
    A["max 环的 Σf / Σt<br>枚举环：指数级，不可行"] -->|"移项：Σ(mid·t) − Σf < 0"| B["猜 mid<br>判定：存在比值 > mid 的环？"]
    B -->|"点权挂入边终点<br>w(u→v) = mid·t − f_v"| C["新图有负环？<br>SPFA：cnt[v] ≥ n 判定"]
    C -->|"有负环 ⇒ lo = mid<br>无负环 ⇒ hi = mid"| D["30 轮二分收敛<br>输出 hi = 最优比值"]
    style A fill:#ffcdd2
    style D fill:#c8e6c9

从上到下是本题的完整思路链：左列说明每一步消除了什么瓶颈——第一步把指数级的环枚举换成单个 $mid$ 的判定问题，第二步把「存在比值更大的环」换成图论里成熟的负环判定，第三步利用单调性把判定问题还原成数值答案。读者对照代码时，可以逐层确认 Mermaid 图中每个箭头对应 main.py 里的哪一段：边权变换对应 graph_adj 推导式，负环判定对应 has_neg_cycle，二分方向对应 lo/hi 的更新。