题目理解

这是一个关于行李传送系统的周期性问题：

• 有 $n$ 个平台，编号 $0$ 到 $n-1$（代码中做了 $-1$ 转换）
• 每个平台有若干条出边（传送带），按顺序循环使用
• 行李从平台 $0$ 出发，沿着当前选择的传送带移动
• 问：最少处理多少行李后，所有平台的传送带指针都回到初始状态

解题思路

关键观察

1. 每个平台的周期：平台 $i$ 有 $d_i$ 条出边，那么每经过 $d_i$ 个行李，它的指针就循环一次
2. 行李的分布：不是每个行李都经过所有平台，不同平台被访问的频率不同
3. 系统复位的条件：所有平台同时完成整数次循环

数学模型

设 $f_i$ 表示平均每个行李经过平台 $i$ 的次数。

根据流量守恒：

• 平台 $0$：$f_0 = 1$（每个行李都从这里开始）
• 对于平台 $i$：流入量 = 流出量
• 具体地：$f_j = \sum_{i \to j} \frac{f_i}{d_i}$，其中 $d_i$ 是平台 $i$ 的出度

核心结论

平台 $i$ 完成一次循环需要的行李数是 $d_i$（如果 $d_i > 0$），但因为它平均每行李被访问 $f_i$ 次，所以实际需要的行李数是使得 $f_i \times T$ 是 $d_i$ 的倍数的最小 $T$。

即：$f_i \times T \equiv 0 \pmod{1}$ 对于所有 $i$ 成立的最小 $T$。

这等价于求所有 $\frac{1}{f_i}$ 的最小公倍数。

代码解析

from math import gcd
from fractions import Fraction

def lcm(a, b):
    return a * b // gcd(a, b)

N = int(input())
g = [[] for _ in range(N)]
for i in range(N):
    L = list(map(int, input().split()))
    for j in range(L[0]):
        g[i].append(L[j + 1] - 1)  # 转换为0-indexed

# f[i] 表示平均每个行李经过平台i的次数
f = [Fraction(0) for _ in range(N)]
f[0] = 1  # 每个行李都从平台0开始

# 计算每个平台的平均访问次数
for i in range(N):
    deg = len(g[i])
    for j in g[i]:
        f[j] += f[i] / Fraction(deg)

# 找所有分母的最小公倍数
ans = 1
for i in range(N):
    a, b = f[i].as_integer_ratio()
    ans = lcm(ans, b)

print(ans)

算法步骤

1. 建图：读取输入并构建邻接表
2. 流量计算：使用分数精确计算每个平台的平均访问次数
3. 求最小公倍数：所有分数分母的LCM就是答案

为什么这样工作？

• 平台 $i$ 平均每行李被访问 $f_i = \frac{p_i}{q_i}$ 次
• 要让平台 $i$ 完成整数次循环，需要行李数 $T$ 满足 $f_i \times T$ 是整数
• 即 $T$ 是 $q_i$ 的倍数
• 所以 $T$ 是所有 $q_i$ 的最小公倍数

样例验证

样例1

7
3 2 3 5
2 3 6
3 5 6 7
1 6
1 7
0
0

计算得到的 $f$ 值分母的LCM是6，输出6 ✓

样例2

3
0
1 3
0

$f$ 值分母都是1，LCM是1，输出1 ✓

复杂度分析

• 时间复杂度：$O(n^2)$（分数运算有额外开销，但 $n \leq 100$ 可接受）
• 空间复杂度：$O(n)$

总结

这个解法巧妙地将周期性问题转化为分数运算和最小公倍数问题，利用流量守恒精确计算每个平台的访问频率，最终通过求分母的LCM得到系统复位的最小周期。