Stacker Crane problem

最近和 Chao 导做的一个图上机器人运输问题。

考虑一个这样的问题：

考虑一个 $n$ 点 $m$ 边的图，边长随意，有 $q$ 个物品，第 $i$ 个需要从 $s_{i}$ 移动到 $t_{i}$ ，有一个机器人来运输物品，拿起放下的时间不计，但每当拿起一个物品后，不能中途放下，最后需要回到初始节点，最小化移动距离。

其实可以发现这个问题和 $S T S P (S t e i n e r T S P)$ ，即需要访问完图里某些特定节点回到起点的最小化距离，很类似。当 $s_{i} = t_{i}$ 的时候就一样了。

首先可以考虑几种特殊的情况：链上和环上。这两个问题都在19xx年的时候就被证明可以规约到 $M S T (最小生成树)$ 问题，不过问题是环上的证明用了一种非常有技巧性的数学证明。而这种证明方法后面我们尝试并不能拓展到图上，哪怕是一个日字型。所以后来我们又重新从流和cycle basis的方向入手，找到了新的证明方法。

先来讲讲原来的链做法，我们先只考虑所有的 $(s_{i}, t_{i})$ ，这些移动已经有了，我们只是加一些边把这些链连接起来。

我们考虑每一条边 $i$ ，左右点是 $u_{v}, v_{i}$ ，有多少次从左往右走过，设为 $a_{i}$ ，有多少次从右往左走过，设为 $b_{i}$ , 那么很容易可以发现在最后的方案里我们会多走几次使得最后的 $a_{i}^{'} = b_{i}^{'}$ 。
注意一个点是，我们多走的这些边是一条一条的，但原来的链是不能断开的，即走起来不能中间停下。

可以发现我们要满足两个要求：1、每条边的 $a_{i}^{'} = b_{i}^{'}$ 。2、整个图联通。

如果我们设 $ϕ_{i} = max (a_{i}, b_{i}, 1)$ ，如果忽略两侧无用的边，只考虑所有物品间的边，那么最后我们一定是走到 $a_{i}^{'} = b_{i}^{'} = p h i_{i}$ ，1是需要连接几个运输的连通块之间，保证连通性。这个证明是比较显然的，如果我们 $a_{i}^{'} = b_{i}^{'} = ϕ_{i} + k (k > 0)$ ，那么我们一定可以调整移动方式，将之前的一次从 $v_{i} \to u_{i}$ ，然后处理 $u_{i}$ 左侧，然后再从 $u_{i} \to v_{i}$ ，处理 $v_{i}$ 右侧；变成处理 $v_{i}$ 右侧， $v_{i} \to u_{i}$ ，处理 $u_{i}$ 左侧。这样只少了一次 $(u_{i}, v_{i})$ ，不改变正确性。

而且我们显然不会使得 $a_{i}^{'} > ϕ_{i}$ ，这也是很显然的一个，就是除了我们的request，每条边的两个方向的move是可以相互cancel的，所以每条边除了request以外只会有一个方向的move。

那么我们加上这些一条条的边（或者说这些边边长都为1）,这时候我们已经保证要求1，且此时的cost花费是最小的，那么我们只需要目前加了边之后的所有联通快联通起来，直接跑mst即可。

为什么mst是对的，而不是 $a \to b \to c \dots \to a$ 这样一个环呢？因为这时候是一条链，所以是等价的。

复杂度显然不超过 MST 的复杂度，这就是链的做法。

接下来是环的做法。

我们考虑环和链有什么区别：

首先 $(s_{i}, t_{i})$ 显然选择较短的一侧路径就行了。

我们发现这时候不是 $a_{i}^{'} = b_{i}^{'}$ 了，而是 $\forall i, a_{i}^{'} - b_{i}^{'} = k$ ，即最后所有的边不是抵消，而是恰好形成 $k$ 轮绕整个环的路径。

那么一个显然的想法是直接枚举 $k$ ，但显然 $k$ 的值可能很大，每次枚举之后都需要做一次mst，显然是不行的。
为什么最小生成树可以？因为如果走一个环，那么显然就是在 $k + 1 / - 1$ 的时候会被考虑到。所以剩下的联通一定也是一棵树。

但 Frederickson 的论文证明了，设 $x_{1}$ 是满足边的平衡时cost最小的 $k$ , $x_{2}$ 是满足边的平衡且整个图联通的时候cost最小的 $k$ 。可以证明 $| x_{1} - x_{2} | \leq 1$ .

proof

所以我们只需要找到 $x_{1}$ ，枚举三个值即可。

对于图的情况，我们考虑cycle basis，即将整个图分解成 $r = m - n + 1$ 个环。那么这时候，对于一个环，显然还是满足上面一个环的情况，而所有合法的移动方案的 $a, b$ 的差都可以看做这些环的 $k$ 的线性组合。分解的方法也很简单，找一颗mst，那么枚举非树边和树上的链就构成了一个环。

但这时候我们发现之前的证明在此处并不适用，两个环的时候的最优值的不等式就已经无法处理了。

从另外一个方式考虑。

上面我们加的边，其实和flow是完全一样的。
我们实际上可以将之前的看做flow，一个request就是(t->s)的上下界为1的流。
而我们跑一个最小费用可行流，问题就是仍然不连通，即第二步还没做。那就跑mst即可