问题分析

我们有：

• $n$ 个太空站（编号 $1 \dots n$），地球（$0$），月球（$-1$，实际处理用 $n+1$）
• $m$ 艘太空船，每艘容量 $H_i$，按固定周期在若干站点间循环停靠
• $k$ 个人初始在地球，要全部运到月球
• 每个时间单位，太空船移动到下一个停靠站
• 人只能在整点时刻上下船

目标：求最短的时间 $T$，使得 $k$ 个人都能到月球。

关键思路：时间分层

由于太空船位置随时间周期性变化，我们按时间建立分层图：

• 对每个时间 $t = 0, 1, 2, \dots$ 创建一套节点（地球、各空间站、月球）
• 节点 $(station, t)$ 表示在时刻 $t$ 位于该站点

建图方法：

1. 站内停留：
   $(station, t) \to (station, t+1)$，容量 $+\infty$
   → 人可以在空间站等待

2. 太空船移动：
   如果太空船 $i$ 在时刻 $t$ 在站 $u$，时刻 $t+1$ 在站 $v$，则连边：
   $(u, t) \to (v, t+1)$，容量 $H_i$
   → 太空船可运送最多 $H_i$ 人

3. 源点和汇点：

   • 源点 $S$ 连接 $(earth, 0)$，容量 $k$
   • 每个时刻的月球节点连接汇点 $T$，容量 $+\infty$

算法框架

由于不知道最小时间 $T$，需要枚举答案：

1. 从 $T = 0$ 开始，逐步增加 $T$
2. 对每个 $T$：
   • 构建分层图（时间 $0 \dots T$）
   • 计算 $S$ 到 $T$ 的最大流
   • 如果最大流 = $k$，说明 $T$ 天内可以运完所有人，输出 $T$
3. 如果 $T$ 超过某个上界仍未找到解，输出 $0$（无解）

复杂度分析

• 节点数：$O(T \cdot (n+2))$
• 边数：$O(T \cdot (n + m))$
• 最大流算法（Dinic）：$O(\text{节点数}^2 \cdot \text{边数})$
• 在 $n \leq 13, m \leq 20, k \leq 50$ 时，$T$ 不会太大（几百以内），完全可行

样例验证

输入：

2 2 1
1 3 0 1 2
1 3 1 2 -1

太空船信息：

• 船1：容量1，路线 $0 \to 1 \to 2 \to 0 \to 1 \to 2 \dots$（周期3）
• 船2：容量1，路线 $1 \to 2 \to -1 \to 1 \to 2 \to -1 \dots$（周期3）

枚举 $T$：

• $T=1,2,3,4$：最大流=0，无法到达月球
• $T=5$：最大流=1，可以运完

方案（可能）：

• 时刻0：人在地球
• 时刻1：乘船1到站1
• 时刻2：乘船1到站2
• 时刻3：在站2换乘船2
• 时刻4：乘船2到月球
• 时刻5：到达月球

输出：5

算法步骤

1. 读入 $n, m, k$ 和太空船信息
2. 预处理每艘船在每个时刻的位置
3. 枚举 $T = 0, 1, 2, \dots$ 直到上界：
   • 构建分层图（时间 $0..T$）
   • 添加边：
     • 站内停留边
     • 太空船移动边
     • 源点→$(earth,0)$，容量 $k$
     • 所有 $(moon,t)$→汇点，容量 $\infty$
   • 跑最大流
   • 如果流值 = $k$，输出 $T$ 并结束
4. 如果超过上界未找到解，输出 $0$

上界估计

最坏情况：$k$ 个人一次只能运 $1$ 人，需要 $k$ 趟，每趟可能需 $O(n)$ 时间
→ 上界可设为 $k \cdot (n+2) \cdot \text{最大周期}$ 的几倍，或直接设几百。

总结

这道题通过时间分层将动态的太空船移动问题转化为静态的网络流图，结合枚举答案找到最短时间，是分层图网络流的典型应用。关键在于将"时间"这一维度显式地建模到图结构中。