

$13.$星际转移问题

题目

由于人类对自然资源的消耗，人们意识到大约在 $2300$ 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，$2177$ 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。

现有 $n$ 个太空站位于地球与月球之间，且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 $i$ 只可容纳 $H[i]$个人。每艘太空船将周期性地停靠一系列的太空站，例如：$(1，3，4)$ 表示该太空船将周期性地停靠太空站 $134134134…$。每一艘太空船从一个太空站驶往任一太空站耗时均为 $1$。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

对于给定的太空船的信息，找到让所有人尽快地全部转移到月球上的运输方案。

无解时输出 $0$

题解

我觉得这题的解法挺神奇的_{，其实说白了就是个套路}。

首先如果地球到月球没有路径就是无解的，直接先特判掉。

然后发现似乎无法直接求出最快的天数，由于_猜到天数比较少，所以可以考虑与之前的魔术球问题类似的方法求得答案，就是一个个枚举答案（不二分的原因在魔术球问题中已经有所提及）。

对每一个点 $u$ 的每一天 $i$ 拆成点 $u_i$ ，为了表示方便，将月球编号为 $N + 1$。

假设当前枚举到了第 $n$ 天，考虑如何对这一天继续加边。

• 由$S$ 向 $0_n$ 连容量为 $inf$ 的边, 表示地球每天可以有无数的人移民。
• 由 $(N+1)_n$向 $T$ 连容量为 $inf$ 的边，表示月球每天可以接受无数的人。
• 对所有空间站 $i$ ，连边 $(i_{n-1}, i_n)$，容量为 $inf$，表示空间站可以让前一天的所有人今天继续留在这里。
• 对所有飞船 $x$，设其前一天在的空间站为 $stat_1$, 这一天在 $stat_2$，那么连边 $(stat_{1_{n-1}}, stat_{2_n)}$，容量为$H[x]$ ，表示飞船在这天可以将$stat_1$中的人载最多$H[x]$到$stat_2$。

第一次使最大流不少于地球移民人数的那天为答案。