最优高铁环

形式化题目

有五种车次，速度只由开头的字母决定：S 为 1000，G 为 500，D 为 300，T 为 200，K 为 150。一条行车路线由若干车次用 - 连接而成，它的速度和是各车次速度之和（例如 T120-D135-S1 的速度和为 200+300+1000=1500，与编号大小无关）。

给出 $M$ 条行车路线。若路线 A 的末尾车次与路线 B 的开头车次相同，A、B 就能首尾相接；若干条路线依次相接回到起点则构成一个高铁环，环的值是

\frac{\text{环上各条路线的速度和之和}}{\text{环上路线的条数}}\text{。}

求所有高铁环的值的最大值，四舍五入到最接近的整数输出；若不存在任何环，输出 $-1$ 。

数据范围： $0 < M \leqslant 50000$ ，每条路线车次个数不超过 20，保证结果不超过 $2^{31}-1$ 。

样例解释：三条路线 T120-D135-S1（和 1500）、S1-G12（和 1500）、G12-K856-T120（和 850）。T120 同时出现在第一条的开头与第三条的末尾，S1、G12 分别把三条路线串起来，构成环，环的值为 $(1500+1500+850)/3 = 1283.33\ldots$ ，四舍五入得 $1283$ 。

正解

思路

第一步：把路线缩成一条边。 一条路线能被接到哪里、又能接谁，完全由它的末尾车次和开头车次决定，中间车次只贡献速度和。因此把每个车次看成一个点，每条行车路线看成首尾两点之间的一条无向边：边权为该路线的速度和 $s$ ，走这条边就代表"用掉这一条路线"。样例对应的图如下：

graph LR
    T120 -- "1500 (T120-D135-S1)" --- S1
    S1 -- "1500 (S1-G12)" --- G12
    G12 -- "850 (G12-K856-T120)" --- T120

于是"一个高铁环"就是这张图中的一个环，"环的值"就是环上边权的平均值： $\dfrac{\sum_{e \in C} s_e}{|C|}$ （注意分母是路线条数，不是车次个数）。“用到的路线可以重复"正对应"图上的边可以重复走”，图本身天然支持这一点。

第二步：朴素做法与瓶颈。 最直接的想法是枚举每个环算平均值——环可能极长、数量指数级，完全不可行。这是经典的01 分数规划模型：最大化"权值和 ÷ 个数"。

第三步：01 分数规划转判定。 设某个环 $C$ 的平均值为 $avg(C) = \dfrac{\sum s_e}{|C|}$ ，则

avg(C) \geqslant \frac{w}{2} \iff \sum_{e \in C} \bigl(2 s_e - w\bigr) \geqslant 0\text{。}

把每条边的权换成 $2 s_e - w$ 后，“存在平均值 $\geqslant \frac{w}{2}$ 的环"就等价于"图中存在正环”（权值和 $> 0$ 的回路；把所有边权取相反数，也就是判负环）。 $w$ 是整数，权重和、平均值都是有理数，标准的 01 分数规划套路：二分答案，每次判定用SPFA 判（负）环。

第四步：处理"四舍五入"这个坑。 最优平均值为 $x$ 时，四舍五入的结果是 $\lfloor x + 0.5 \rfloor$ 。设答案为整数 $r$ ，则 $x$ 四舍五入后 $\geqslant r$ 当且仅当 $x \geqslant r - 0.5$ ，而

x \geqslant r - \frac{1}{2} \iff \sum_{e \in C} \bigl(2 s_e - (2r - 1)\bigr) \geqslant 0\text{。}

所以不需要对 $\frac{w}{2}$ 做浮点二分：直接在整数 $r$ 上二分，判定条件为整数不等式 $\sum_{e \in C} \bigl(2 s_e - (2r-1)\bigr) \geqslant 0$ ，全程无浮点误差。找到最大的、判定成立的 $r_{\max}$ 即答案。速度和的最大值为 $20 \times 1000 = 20000$ ，平均值不超过 $20000$ ，二分上界取 $20001$ 即可（下界取 $1$ ：任何环的平均速度和都是正的， $r=1$ 的判定恒成立）。

第五步：把“ $\geqslant 0$ 的环”精确化成 SPFA 能判的“严格正环”。 SPFA 的计数法只能找严格正环（权值和 $> 0$ 的回路），而这里需要判的是 $\geqslant 0$ 。好在 $\sum_{e \in C}\bigl(2 s_e - (2r-1)\bigr)$ 是整数，且环的边数 $|C| \leqslant n$ ，所以两边同乘 $n+1$ 再加 $|C|$ 不改变结论：

\sum_{e \in C}\bigl(2 s_e - (2r-1)\bigr) \geqslant 0 \iff (n+1)\sum_{e \in C}\bigl(2 s_e - (2r-1)\bigr) + |C| > 0\text{，即}\sum_{e \in C} a_e - (n+1)(2r-1) > 0\text{，}

其中 $a_e = (n+1)\cdot 2 s_e + 1$ 是建图时就存好的边权。于是判定变成：把每条边权换成 $a_e - (n+1)(2r-1)$ 后判严格正环——最优平均值恰好为 $k+0.5$ 的边界情形也能被正确舍入，没有任何精度或边界隐患。

第六步：判正环的实现。 图可能不连通，所以把所有点的初始距离设为 $0$ （等价于建一个连向所有点的超级源点），跑 SPFA 最长路；一旦某个点的最长路已经用掉 $n$ 条边（前驱链上点必然重复），说明存在严格正环。若无任何正环，说明图里根本没有环，此时输出 $-1$ ；为了让 $-1$ 只在“真的没有环”时出现，二分下界取 $1$ ——只要图中还有环，其速度和必为正、平均值必大于 $0.5$ ， $r=1$ 的判定必然成立，因此二分结束后 $r_{\max}=1$ 恰好对应“无环”。

代码

cpp

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113/**
 * 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 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 每条高铁路线建成一条有向边：开头车次 -> 末尾车次
// 边上存 a = (n+1)*(2*速度和) + 1

int n;                       // 车次种类数（节点数）
vector<pair<int, ll> > adj[5005];

// 判断是否存在平均值 >= r - 0.5 的环：对边权 a - (n+1)*(2r-1) 判严格正环
bool has_cycle_avg_ge(int r) {
    // 边权 a - (n+1)*(2r-1)
    ll offset = (ll)(n + 1) * (2LL * r - 1);
    // 复制一份偏移后的图判断正环
    // 直接改全局 adj 不方便，这里重新做一次 SPFA
    vector<ll> dist(n, 0);
    vector<int> edge_cnt(n, 0);
    vector<char> in_queue(n, 1);
    deque<int> q;
    for (int i = 0; i < n; i++) q.push_back(i);
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        in_queue[u] = 0;
        ll du = dist[u];
        for (size_t i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first;
            ll a = adj[u][i].second;
            ll nd = du + a - offset;
            if (nd > dist[v]) {
                dist[v] = nd;
                edge_cnt[v] = edge_cnt[u] + 1;
                if (edge_cnt[v] >= n) return true;
                if (!in_queue[v]) {
                    if (!q.empty() && nd > dist[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    in_queue[v] = 1;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;
    cin.ignore();

    map<string, int> node_id;
    vector<pair<string, string> > raw;   // 每条路线 (开头车次, 末尾车次)
    vector<int> raw_s;                   // 每条路线的速度和

    for (int line = 0; line < m; line++) {
        string s;
        getline(cin, s);
        // 拆成 codes
        vector<string> codes;
        string cur;
        for (size_t i = 0; i <= s.size(); i++) {
            if (i == s.size() || s[i] == '-') {
                codes.push_back(cur);
                cur.clear();
            } else {
                cur.push_back(s[i]);
            }
        }
        int sum = 0;
        for (size_t i = 0; i < codes.size(); i++) {
            char c = codes[i][0];
            if (c == 'S') sum += 1000;
            else if (c == 'G') sum += 500;
            else if (c == 'D') sum += 300;
            else if (c == 'T') sum += 200;
            else if (c == 'K') sum += 150;
        }
        raw.push_back(make_pair(codes[0], codes[codes.size() - 1]));
        raw_s.push_back(sum);
        if (node_id.find(codes[0]) == node_id.end())
            node_id[codes[0]] = (int)node_id.size();
        if (node_id.find(codes[codes.size() - 1]) == node_id.end())
            node_id[codes[codes.size() - 1]] = (int)node_id.size();
    }

    n = (int)node_id.size();
    ll scale = n + 1;
    for (size_t i = 0; i < raw.size(); i++) {
        int u = node_id[raw[i].first];
        int v = node_id[raw[i].second];
        adj[u].push_back(make_pair(v, scale * 2LL * raw_s[i] + 1));
    }

    int lo = 1, hi = 20001;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (has_cycle_avg_ge(mid)) lo = mid + 1;
        else hi = mid;
    }
    int ans = (lo > 1) ? lo - 1 : -1;
    cout << ans << "\n";
    return 0;
}

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98#!/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-07-05 21:47
# update_at: 2026-10-02 02:23

import sys
from collections import deque

SPEED = {"S": 1000, "G": 500, "D": 300, "T": 200, "K": 150}  # 五种车次的速度


def build_graph(lines_txt: list[str]) -> tuple[int, list[list[tuple[int, int]]]]:
    """把每条行车路线建成一条有向边，返回 (点数, 邻接表)。

    连接规则是有向的：前一条路线的末尾车次接到后一条的开头车次，
    所以路线对应"开头车次 → 末尾车次"的有向边，高铁环必须顺着箭头走。
    边上存 a = (n+1)·(2×速度和) + 1，n 是点数；放大加一是为了让
    "权值和 ≥ 0 的环"精确等价于"放大后权值和 > 0 的正环"（见判定函数）。
    """
    node_id: dict[str, int] = {}
    edges: list[tuple[str, str, int]] = []
    for line in lines_txt:
        codes = line.split("-")
        s = sum(SPEED[code[0]] for code in codes)  # 车次速度只看字母，与编号无关
        edges.append((codes[0], codes[-1], s))
        node_id.setdefault(codes[0], len(node_id))
        node_id.setdefault(codes[-1], len(node_id))
    n = len(node_id)
    scale = n + 1  # 环的权值和是整数，放大 n+1 倍后每条边加 1 不会改变 ≥ 0 的判定
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for head, tail, s in edges:
        u, v = node_id[head], node_id[tail]
        adj[u].append((v, scale * 2 * s + 1))
    return n, adj


def has_cycle_avg_ge(n: int, adj: list[list[tuple[int, int]]], r: int) -> bool:
    """判断是否存在平均值 ≥ r − 0.5 的高铁环（SPFA 判正环）。

    环 C 满足 avg(C) ≥ r − 0.5 ⟺ Σ(2s−(2r−1)) ≥ 0。记 scale = n+1，由于
    Σ(2s−(2r−1)) 是整数，"≥ 0" ⟺ "scale×它 + |C| > 0"，后者恰好是对
    边权 a−scale·(2r−1) 判严格正环——SPFA 的计数法只能找严格正环，
    这个放大加一的恒等变换把边界情形（平均值恰为 k+0.5）也判对。
    """
    offset = (n + 1) * (2 * r - 1)
    dist = [0] * n          # 虚拟超级源（连向所有点）出发的最长路，初值全 0
    edge_cnt = [0] * n      # 当前最长路用掉的边数，达到 n 说明 predecessor 链成环
    in_queue = bytearray(n)
    queue = deque(range(n))  # 所有点同时入队，等价于一个超级源点
    for u in range(n):
        in_queue[u] = 1
    while queue:
        u = queue.popleft()
        in_queue[u] = 0
        du = dist[u]
        au = adj[u]
        for v, a in au:
            nd = du + a - offset
            if nd > dist[v]:
                dist[v] = nd
                edge_cnt[v] = edge_cnt[u] + 1
                if edge_cnt[v] >= n:  # 链上有 n 条边 ⇒ 前驱链成环 ⇒ 严格正环
                    return True
                if not in_queue[v]:
                    # SLF 优化：比队首大就插队首，正环能让 dist 更快抬升
                    if queue and nd > dist[queue[0]]:
                        queue.appendleft(v)
                    else:
                        queue.append(v)
                    in_queue[v] = 1
    return False


def rounded_best_avg(n: int, adj: list[list[tuple[int, int]]]) -> int:
    """整数二分四舍五入后的答案 r：判定条件是存在平均值 ≥ r − 0.5 的环。"""
    lo, hi = 1, 20001  # 平均值 ≤ 单条路线速度和上限 20000，hi 是取不到的上界
    while lo < hi:
        mid = (lo + hi) // 2
        if has_cycle_avg_ge(n, adj, mid):  # 判"平均值 ≥ mid − 0.5"
            lo = mid + 1
        else:
            hi = mid
    # lo 是第一个判定不成立的 r，最大可行值 = lo − 1；
    # lo 仍为 1 说明 r=1（阈值 0.5）都不成立，图中没有任何环
    return lo - 1 if lo > 1 else -1


def solve() -> None:
    rows = sys.stdin.buffer.read().decode().replace("\r", "").split("\n")
    m = int(rows[0])
    n, adj = build_graph(rows[1 : m + 1])
    print(rounded_best_avg(n, adj))


if __name__ == "__main__":
    solve()

复杂度

建图 $O(M)$ ，点数 $n \leqslant M$ 、边数 $M \leqslant 50000$ 。
SPFA 判正环单次最坏 $O(n \cdot M)$ ，二分约 $\log_2 20000 \approx 15$ 轮，总复杂度 $O(\log V \cdot n \cdot M)$ ——与 C++ 标准解法同阶。加了 SLF 优化后，本题实际数据上 Python 也能在限内跑完。
空间 $O(n + M)$ 。

总结

建模：行车路线 → 首尾车次之间的无向边（权 = 速度和），高铁环 → 图中的环，注意"环的值"的分母是路线条数，与一条路线里有几个车次无关。
算法：01 分数规划 + SPFA 判正环， $O(\log V \cdot n \cdot M)$ 。
两个易错点：
1. 四舍五入——不要对平均值做浮点二分，改为直接二分答案 $r$ 、判“平均值 $\geqslant r - 0.5$ ”； $\sum(2s-(2r-1))$ 是整数，同乘 $n+1$ 再加环长即可把 “ $\geqslant 0$ ”精确化为 SPFA 能判的“严格正环”，避开所有边界与精度问题。
2. 无环输出 $-1$ ——把二分下界压到 $1$ ，让"判定成立的最大 $r$ "为 $1$ 时恰好对应无环。
Python 实现要点：SPFA 主循环里把 dist[u]、adj[u] 提到局部变量，手动内层循环代替 enumerate，这是 Python 判环能否过时限的关键。

图示解析

整体解法路线

flowchart LR
    A["M 条行车路线"] --> B["缩点连边<br>每条路线 = 首尾车次间的无向边<br>权 = 速度和"]
    B --> C["01 分数规划<br>二分四舍五入后的答案 r"]
    C --> D["判定：边权 aₑ=(n+1)·2s+1 换成<br>aₑ−(n+1)(2r−1) 后有无严格正环<br>（精确等价于存在平均值 ≥ r−0.5 的环）"]
    D -- "有" --> E["r 还能更大<br>r = r + 1"]
    E --> D
    D -- "无" --> F["r 就是答案<br>（r=1 说明无环，输出 −1）"]

二分判定在样例上的取值

以样例（三条路线构成环，平均 $1283.33\ldots$ ）为例，列出二分过程中判定 $avg \geqslant r-0.5$ 的结果：

二分到的 $r$	判定阈值 $r-0.5$	边权 $2s-(2r-1)$ 后存在正环？	结论
$10001$	$10000.5$	否（边权全为 $2s-20001<0$ ）	答案更小，往左
$5001$	$5000.5$	否	答案更小，往左
$2501$	$2500.5$	否	答案更小，往左
$1251$	$1250.5$	是（环均值 $1283.33 \geqslant 1250.5$ ）	答案更大，往右
$1284$	$1283.5$	否（ $1283.33 < 1283.5$ ）	答案更小，往左
$1283$	$1282.5$	是（ $1283.33 \geqslant 1282.5$ ）	收敛

二分收敛到最大的可行 $r = 1283$ ，正是四舍五入后的正确答案；观察中间行： $r=1284$ 的阈值 $1283.5$ 恰好被 $1283.33$ 卡掉——这就是"四舍五入等于判定 $r-0.5$ "的具体体现。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

整体解法路线

二分判定在样例上的取值