每站把两条入边与两条出边配成接续即得线路的分解;先取局部最省配对得到若干环,把翻转每站的代价当边权,用最小生成树把环并成一个完成枚举。
OJ: roj
题目 ID: 1739
难度:提高+/省选-
标签:欧拉回路最小生成树Kruskalpython
创建: 2026-10-07 20:33
更新: 2026-10-07 20:33
形式化题目
有
注意
正解
思路
第一步:把「行程」翻译成车站上的接续关系。
拿到一条线路到站后,下一趟要坐哪条,只由「到达这个车站时,这里还没坐过的出边」决定。
但更省事的看法是:合法的行程在每个车站把两条入边与两条出边一一配对,
第二步:把总时间拆成与配对无关的部分加可以逐站计算的部分。
线路
与「已经过了几天」无关——差的总是
其中
第三步:先在每站取局部最优,问题变成「把若干小环并成一个大环」。
其中
关键在于翻转一个车站对全局环结构做了什么:它把两条入边
顺带一提:翻转顺序无关紧要,因为「同一连通块里的环全部合并」这件事只取决于翻转集合, 与先后次序无关;而环图连通后翻转集自然对应一个大环。
第四步:处理
因为
代码
#!/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()/**
* 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;
}复杂度
时间
总结
本题的链条是「行程
关于本题材料
- 题面与数据来自本站对《信息学奥赛一本通 · 高手训练》第 7 章(欧拉回路)中 「1739 观光巴士」的重建,素材中带有数据生成脚本,第一组数据为本题样例、 第二组为原始题面第二个样例,均通过。
- 参考实现(素材
std.cpp)在全部 10 组真实数据上与期望输出一致,因此被用作对拍参照; 正式解仍按本 skill 的 C++ 风格重写,不照抄。 - 题面中「
且每天 小时」存在歧义;全部真实数据的 都取在 ,因此两种读法答案相同,本文按「时刻取模 」的读法处理。