自动搬运

查看原文

来自洛谷，原作者为

	meyi 明日黄花

搬运于2025-08-24 22:46:54，当前版本为作者最后更新于2025-03-19 05:12:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于每个有传送带的平台 $i$，系统复位的条件是，到达该平台的行李箱数恰好是 $r_i$​ 的倍数。

直接计算到达每个平台的行李箱数是困难的，但是根据上面的结论，到达每个平台的行李箱数都是其传送带数量的倍数，因此其连接的每条传送带传出的行李箱数也一定相等。

将最开始放在 $1$ 号平台上的一个单位流量视作整体处理过程的基准。接下来，每个平台 $i$ 接收到的流量（记作 $flow_i$）则可以表示：如果我们放出一个单位流量的行李箱，那么平台 $i$ 最终收到的箱子为 $flow_i$ 个单位流量，显然这是个有理数。

对于一个拥有 $r_i$ 条传送带的平台，传送箱子时均分给每条传送带，所以每条传送带传出的流量为

传送带仅从较小编号的平台通向编号更大的平台，这保证了整个系统构成一个 DAG，使得我们可以按编号从小到大开始依次计算 $flow_i$。

对于每个有传送带的平台 $i$，总共处理了 $X$​ 个行李箱后，该平台收到的行李箱数为

由于平台的传送带采用循环调度，只有当上面这个数是 $r_i$ 的倍数时，平台的状态才会复位。换句话说，我们要求

也即

不妨假设 $f_i$ 的最简分数表示为 $\frac{p_i}{q_i}$，其中 $p_i,q_i\in \mathbb{Z}^+$ 且 $\gcd(p_i,q_i)=1$，那么上式等价于

可知

即为答案。

显然 $X$ 的值可能很大，又因本题涉及到分数运算，因此使用 Python 实现。

from fractions import Fraction
from math import lcm

n = int(input())
to = []
for i in range(n):
    to.append([j - 1 for j in list(map(int, input().split()))[1:]])
flow = [Fraction(1)] + [Fraction(0)] * (n - 1)
X = 1
for i in range(n):
    if to[i]:
        f = flow[i] / len(to[i])
        X = lcm(f.denominator, X)
        for j in to[i]: flow[j] += f
print(X)