观光巴士

GitHub跳转原题关系图返回列表

每站把两条入边与两条出边配成接续即得线路的分解;先取局部最省配对得到若干环,把翻转每站的代价当边权,用最小生成树把环并成一个完成枚举。

OJ: roj

题目 ID: 1739

难度:提高+/省选-

标签:欧拉回路最小生成树Kruskalpython

创建: 2026-10-07 20:33

更新: 2026-10-07 20:33

形式化题目

有 nn 个车站、2n2n 条线路。第 ii 条线路的起点是 ⌈i/2⌉\lceil i/2 \rceil,终点是 eie_i, 每天恰好一班,时刻 lil_i 出发,历时 did_i 小时后到站(每天 2424 小时)。 第 11 天 00 时人在 11 号站。求一条「每条线路恰好乘坐一次、最终回到 11 号站」的 行程,使回到 11 号站的时刻最早;输出该最早时刻。

注意 ii 从 11 编号时,第 1,21,2 条线路都从 11 号站出发,第 3,43,4 条都从 22 号站出发…… 即每个车站恰有两条出边;题目保证存在合法行程,于是每个车站也恰有两条入边, 且 ei≠ie_i \neq i(没有自环)。

正解

思路

第一步:把「行程」翻译成车站上的接续关系。

拿到一条线路到站后,下一趟要坐哪条,只由「到达这个车站时,这里还没坐过的出边」决定。 但更省事的看法是:合法的行程在每个车站把两条入边与两条出边一一配对, succ(r)succ(r) 表示「乘坐线路 rr 到站之后接着坐 succ(r)succ(r)」。一次合法行程就是这种配对下 2n2n 条线路构成的一个大环(从 11 号站某条出边出发,走 2n2n 步回到它)。

第二步:把总时间拆成与配对无关的部分加可以逐站计算的部分。

线路 rr 于 lrl_r 出发、lr+drl_r + d_r 到站,班次时刻是 {lr+24k}\{l_r + 24k\}。所以在 ee 之后 接 ff 的等待只由两条线路决定:

W(e,f)=(lf−le−de) mod 24∈[0,24), W(e,f) = \big(l_f - l_e - d_e\big) \bmod 24 \in [0, 24),

与「已经过了几天」无关——差的总是 2424 的整数倍。于是行程总用时

T=∑rdr⏟固定+ls⏟首班候车+∑接续 e→fW(e,f), T = \underbrace{\sum_r d_r}_{\text{固定}} + \underbrace{l_{s}}_{\text{首班候车}} + \sum_{\text{接续 } e \to f} W(e,f),

其中 ss 是首班线路,第 11 天 00 时必须等到 lsl_s 才发车(那一次「接续等待」被 候车替代)。∑dr\sum d_r 与方案无关,可以整块拿走,剩下的部分对每个车站 只依赖落在它身上的两条入边和两条出边,本地可算。

第三步:先在每站取局部最优,问题变成「把若干小环并成一个大环」。

22 号站到 nn 号站各自只有两种配对,代价分别是

cA=W(a,o1)+W(b,o2),cB=W(a,o2)+W(b,o1), c_A = W(a, o_1) + W(b, o_2), \qquad c_B = W(a, o_2) + W(b, o_1),

其中 a,ba,b 是该站的两条入边、o1,o2o_1,o_2 是它的两条出边。每站先取较小的那个,得到一个 初始配对 π0\pi_0,把线路分解成 kk 个环;令 Δv=∣cA−cB∣⩾0\Delta_v = |c_A - c_B| \geqslant 0 为 车站 vv 翻转配对的额外代价。

关键在于翻转一个车站对全局环结构做了什么:它把两条入边 a,ba, b 落的两个环 ring(a)\mathrm{ring}(a)、ring(b)\mathrm{ring}(b) 合并成一个(如果两者本来同环,则是把环拆开, 永远不会更优)。把每个环看成一个点,为每个 ring(a)≠ring(b)\mathrm{ring}(a) \neq \mathrm{ring}(b) 的车站 vv 建一条权为 Δv\Delta_v 的边,那么「翻转集 ⇔\Leftrightarrow 把 kk 个点连通」, 最小额外代价就是这张环图上的最小生成树(Kruskal)。若环图不连通,说明在这个配对下 无论如何都拼不出单环。

顺带一提:翻转顺序无关紧要,因为「同一连通块里的环全部合并」这件事只取决于翻转集合, 与先后次序无关;而环图连通后翻转集自然对应一个大环。

第四步:处理 11 号站和首班。

11 号站有一点特殊:它的两条入边与出边也要配对,但「从 11 号站出发的第一次乘坐」 之前没有接续——那是当天的候车 lsl_s,而原本要接向 ss 的那次接续不发生。 把 11 号站的两种配法各枚举一遍,每种配法里再枚举 ss 取哪条出边(另一条入边继续照常 接向 other\mathrm{other} 即可),外层再取总时间的最小值。

因为 n⩽1000n \leqslant 1000,2n⩽20002n \leqslant 2000 条线路,环图最多 nn 个点、nn 条边, 整个算法是 O(nlog⁡n)O(n \log n),与 1s1 \texttt{s} / 128MB128 \texttt{MB} 的限制相比非常宽裕。

代码

python
#!/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-07 20:29
# update_at: 2026-10-07 20:33

import sys

DAY = 24            # 每天 24 小时,接续等待只由 (l_e + d_e) 与 l_f 对 24 取模决定
INF = 10**18        # 「这个配对下连不成单环」的哨兵

type InEdges = list[list[int]]  # InEdges[v] = 终点是车站 v 的两条线路编号


def wait_cost(dep: list[int], dur: list[int], e: int, f: int) -> int:
    """在 e 号线路到站后接续 f 号线路要等的时长(与已经过了几天无关)。"""
    return (dep[f] - dep[e] - dur[e]) % DAY


def shortest_tour(dep: list[int], dur: list[int], ins: InEdges, first: int) -> int:
    """固定 1 号车站两种配对中的第 first 种,返回坐遍所有线路回到 1 号站的最短用时。"""
    n = len(ins)
    m = 2 * n
    succ = [0] * m                      # succ[r] = 到达车站后接着乘坐的线路
    a, b = ins[0]                       # 1 号车站的两条入边,两条出边是线路 0、1
    succ[a], succ[b] = (1, 0) if first else (0, 1)

    base = 0                            # 其余车站都取当地更省的配对时的等待之和
    delta = [0] * n                     # 车站 v 翻转配对要多花的等待
    for v in range(1, n):
        x, y = ins[v]
        ox, oy = 2 * v, 2 * v + 1       # 车站 v 的两条出边
        cost_x, cost_y = wait_cost(dep, dur, x, ox), wait_cost(dep, dur, y, oy)
        cost_swap = wait_cost(dep, dur, x, oy) + wait_cost(dep, dur, y, ox)
        if cost_x + cost_y <= cost_swap:
            succ[x], succ[y] = ox, oy
            base += cost_x + cost_y
            delta[v] = cost_swap - cost_x - cost_y
        else:
            succ[x], succ[y] = oy, ox
            base += cost_swap
            delta[v] = cost_x + cost_y - cost_swap

    ring = [-1] * m                     # 初始配对把线路拆成若干环,先逐个编号
    ring_cnt = 0
    for r in range(m):
        if ring[r] >= 0:
            continue
        cur = r
        while ring[cur] < 0:
            ring[cur] = ring_cnt
            cur = succ[cur]
        ring_cnt += 1

    # 翻转车站 v 的配对会把 ring[x]、ring[y] 两个环并成一个,代价 delta[v];
    # 要让全部环并成一个,取环图上的最小生成树(同环的两个入边翻转只会拆环,不成边)。
    edges = []                          # (翻转代价, 被合并的两个环)
    for v in range(1, n):
        x, y = ins[v]
        if ring[x] != ring[y]:
            edges.append((delta[v], ring[x], ring[y]))
    edges.sort()

    par = list(range(ring_cnt))
    merges = extra = 0                  # 已合并次数、合并多花的等待
    for w, u, v in edges:
        while par[u] != u:              # 路径减半地找根
            par[u] = par[par[u]]
            u = par[u]
        while par[v] != v:
            par[v] = par[par[v]]
            v = par[v]
        if u != v:
            par[u] = v
            merges += 1
            extra += w
    if merges != ring_cnt - 1:
        return INF                      # 环图不连通,这个配对拿不到单环

    travel = sum(dur)                   # 行驶时长与方案无关,整块计入
    best = INF
    for s in (0, 1):
        other = 1 - s                   # 首班是线路 s,另一条入边的接续照常发生
        pin = next(r for r in (a, b) if succ[r] == other)
        total = travel + dep[s] + wait_cost(dep, dur, pin, other) + base + extra
        best = min(best, total)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    dep, dur = [0] * (2 * n), [0] * (2 * n)  # 线路 i 的每日发车时刻 l_i 与行驶时长 d_i
    ins: InEdges = [[] for _ in range(n)]
    for i in range(2 * n):
        end, l, d = next(data), next(data), next(data)   # 题面的 e_i、l_i、d_i
        ins[end - 1].append(i)
        dep[i], dur[i] = l, d

    # 1 号车站的两种入边接法都要试,各自内部再枚举首班线路,取总用时较小者
    print(min(shortest_tour(dep, dur, ins, first) for first in (0, 1)))


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-07 20:29
 * update_at: 2026-10-07 20:33
 */
// 一本通 1739《观光巴士》。
// 「每条线路恰好坐一次并回到 1 号站」= 在每个车站把两条入边与两条出边配成接续,
// 使接续关系构成一个大环。每站先取当地更省的配对(得到若干小环),
// 再把「翻转某个车站的配对」看成合并两个环的边,用最小生成树把环并成一个。
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1005;                // 车站数上限 n <= 1000
const int MAXM = 2 * MAXN;            // 线路数上限 2n
const ll INF = 1000000000000000000LL; // 「该配对下连不成单环」的哨兵

int n;                  // 车站数
int m;                  // 线路数,恒为 2n
ll dep[MAXM];           // 线路 i 的每日发车时刻 l_i
ll dur[MAXM];           // 线路 i 的行驶时长 d_i
int arrive_in[MAXN][2]; // arrive_in[v] = 终点是车站 v 的两条线路编号,车站从 0 号开始编号
int arrive_cnt[MAXN];   // 车站 v 已登记的入边条数
ll sum_dur;             // 所有线路的行驶时长之和(与行程方案无关,整块计入答案)
int succ[MAXM];         // 当前接续方案:succ[r] = 到达后接着乘坐的线路编号
int ring[MAXM];         // 初始配对下线路 r 所在环的编号
int par[MAXM];          // Kruskal 并查集,规模是环数
ll delta[MAXN];         // 车站 v 改用另一种配对要多花的等待小时数

struct Edge {
    ll w; // 翻转这个车站的配对要多花的等待
    int u; // 翻转后合并进来的一个环
    int v; // 翻转后合并进来的另一个环
};
Edge edge[MAXN];        // 每个非 1 号车站至多贡献一条合并边

// 在 e 号线路到站后接续 f 号线路所需的等待小时数;
// 只依赖这两条线路((l_e + d_e) 与 l_f 之差对 24 取模),与已经过了几天无关。
ll wait_cost(int e, int f) {
    ll w = dep[f] % 24 - (dep[e] + dur[e]) % 24;
    if (w < 0) w += 24;
    return w;
}

// 合并边按代价升序排序,供 Kruskal 使用。
bool cmp_edge(const Edge &x, const Edge &y) {
    return x.w < y.w;
}

// 并查集找根,带路径减半。
int find_root(int x) {
    while (par[x] != x) {
        par[x] = par[par[x]];
        x = par[x];
    }
    return x;
}

// 固定 1 号车站的配对方式 p0(两条入边分别接向哪条出边),
// 返回坐遍所有线路并回到 1 号站的最短用时;该配对下连不成单环时返回 INF。
ll shortest_tour(int p0) {
    // 1 号车站的两条出边固定是线路 0 与线路 1
    succ[arrive_in[0][0]] = p0 ? 1 : 0;
    succ[arrive_in[0][1]] = p0 ? 0 : 1;

    ll base = 0; // 2..n 号车站都取当地更省的配对时的总等待
    for (int v = 1; v < n; ++v) {
        int a = arrive_in[v][0], b = arrive_in[v][1];
        int outA = 2 * v, outB = 2 * v + 1; // 车站 v 的两条出边
        ll costA = wait_cost(a, outA) + wait_cost(b, outB);
        ll costB = wait_cost(a, outB) + wait_cost(b, outA);
        if (costA <= costB) {
            succ[a] = outA;
            succ[b] = outB;
            base += costA;
            delta[v] = costB - costA; // 翻转该车站要多花的等待
        } else {
            succ[a] = outB;
            succ[b] = outA;
            base += costB;
            delta[v] = costA - costB;
        }
    }

    // 初始配对把所有线路分拆成若干环,先给每个环编号
    for (int r = 0; r < m; ++r) ring[r] = -1;
    int ring_cnt = 0;
    for (int r = 0; r < m; ++r) {
        if (ring[r] != -1) continue;
        int cur = r;
        while (ring[cur] == -1) {
            ring[cur] = ring_cnt;
            cur = succ[cur];
        }
        ++ring_cnt;
    }

    // 翻转车站 v 的配对会把 ring[in_a] 与 ring[in_b] 两个环并成一个,代价 delta[v];
    // 要在环图上连通所有环,取最小生成树。(同一环内的车站翻转只会把环拆开,不建边)
    int ecnt = 0;
    for (int v = 1; v < n; ++v) {
        int x = ring[arrive_in[v][0]], y = ring[arrive_in[v][1]];
        if (x == y) continue;
        edge[ecnt].w = delta[v];
        edge[ecnt].u = x;
        edge[ecnt].v = y;
        ++ecnt;
    }
    sort(edge, edge + ecnt, cmp_edge);

    for (int i = 0; i < ring_cnt; ++i) par[i] = i;
    int merges = 0;  // 已完成的合并次数
    ll extra = 0;    // 合并带来的额外等待
    for (int i = 0; i < ecnt; ++i) {
        int x = find_root(edge[i].u);
        int y = find_root(edge[i].v);
        if (x == y) continue;
        par[x] = y;
        ++merges;
        extra += edge[i].w;
    }
    if (merges != ring_cnt - 1) return INF; // 环图不连通,这个配对拿不到单环

    // 首班线路 s 的那次「接续等待」被第 1 天 0 时起的候车时间 dep[s] 取代:
    // 另一条入边 pin 照常接向 other,而原本接向 s 的那次接续不再发生。
    ll best = INF;
    for (int s = 0; s < 2; ++s) {
        int other = 1 - s;
        int pin = -1;
        for (int k = 0; k < 2; ++k) {
            int r = arrive_in[0][k];
            if (succ[r] == other) pin = r;
        }
        if (pin < 0) continue;
        ll total = sum_dur + dep[s] + wait_cost(pin, other) + base + extra;
        if (total < best) best = total;
    }
    return best;
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    m = 2 * n;
    for (int i = 0; i < m; ++i) {
        ll e, l, d;
        if (scanf("%lld %lld %lld", &e, &l, &d) != 3) return 0;
        dep[i] = l;
        dur[i] = d;
        sum_dur += d;
        arrive_in[e - 1][arrive_cnt[e - 1]] = i;
        ++arrive_cnt[e - 1];
    }

    ll ans = INF;
    for (int p0 = 0; p0 < 2; ++p0) {
        ll cur = shortest_tour(p0);
        if (cur < ans) ans = cur;
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

时间 O(nlog⁡n)O(n \log n)(两次配对枚举,各自做一次排序 + Kruskal),空间 O(n)O(n)。 n=1000n = 1000 时排序与并查集的开销可忽略,CPython 也远低于 1s1\texttt{s}。

总结

本题的链条是「行程 →\to 每站配对 →\to 环分解 →\to 环图上求生成树」,每一步都把 组合选择的规模压小一层:先是把 2n2n 条线路的排列问题变成每个车站内部的二选一 (这一步用到「每站两条入边两条出边」这个由 ei≠ie_i \neq i 与题面保证的可行性共同推出的结构), 再把「翻转集必须把环图连通」看出来,最后用最小生成树一次性解决。 真正需要小心的只有两处细节:接续等待 W(e,f)=(lf−le−de) mod 24W(e,f) = (l_f - l_e - d_e) \bmod 24 必须取模 (本题数据中 lil_i 都落在 [0,23][0,23],题面写的 li⩽1000l_i \leqslant 1000 只在「每天 2424 小时」这一 自洽读法下有意义),以及首班那次「接续」要被第一天的候车 lsl_s 替代。

关于本题材料

  • 题面与数据来自本站对《信息学奥赛一本通 · 高手训练》第 7 章(欧拉回路)中 「1739 观光巴士」的重建,素材中带有数据生成脚本,第一组数据为本题样例、 第二组为原始题面第二个样例,均通过。
  • 参考实现(素材 std.cpp)在全部 10 组真实数据上与期望输出一致,因此被用作对拍参照; 正式解仍按本 skill 的 C++ 风格重写,不照抄。
  • 题面中「0⩽li⩽10000 \leqslant l_i \leqslant 1000 且每天 2424 小时」存在歧义;全部真实数据的 lil_i 都取在 [0,23][0, 23],因此两种读法答案相同,本文按「时刻取模 2424」的读法处理。