最近和 Chao 导做的一个图上机器人运输问题。
考虑一个这样的问题：
考虑一个 $n$ 点 $m$ 边的图，边长随意，有 $q$ 个物品，第 $i$ 个需要从 $s_i$ 移动到 $t_i$，有一个机器人来运输物品，拿起放下的时间不计，但每当拿起一个物品后，不能中途放下，最后需要回到初始节点，最小化移动距离。
其实可以发现这个问题和 $STSP(Steiner TSP)$，即需要访问完图里某些特定节点回到起点的最小化距离，很类似。当 $s_i=t_i$ 的时候就一样了。
首先可以考虑几种特殊的情况：链上和环上。这两个问题都在19xx年的时候就被证明可以规约到 $MST(最小生成树)$ 问题，不过问题是环上的证明用了一种非常有技巧性的数学证明。而这种证明方法后面我们尝试并不能拓展到图上，哪怕是一个日字型。所以后来我们又重新从流和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、整个图联通。
如果我们设 $\phi_i=\max(a_i,b_i,1)$，如果忽略两侧无用的边，只考虑所有物品间的边，那么最后我们一定是走到 $a’_i=b’_i=phi_i$，1是需要连接几个运输的连通块之间，保证连通性。这个证明是比较显然的，如果我们$a’_i=b’_i=\phi_i+k(k>0)$，那么我们一定可以调整移动方式，将之前的一次从 $v_i\rightarrow u_i$，然后处理 $u_i$ 左侧，然后再从 $u_i\rightarrow v_i$，处理 $v_i$ 右侧；变成 处理 $v_i$ 右侧， $v_i\rightarrow u_i$，处理 $u_i$ 左侧。这样只少了一次 $(u_i,v_i)$，不改变正确性。
而且我们显然不会使得 $a’_i>\phi_i$，这也是很显然的一个，就是除了我们的request，每条边的两个方向的move是可以相互cancel的，所以每条边除了request以外只会有一个方向的move。
那么我们加上这些一条条的边（或者说这些边边长都为1）,这时候我们已经保证要求1，且此时的cost花费是最小的，那么我们只需要目前加了边之后的所有联通快联通起来，直接跑mst即可。
为什么mst是对的，而不是 $a\rightarrow b\rightarrow c…\rightarrow 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|\le 1$.
proof
所以我们只需要找到 $x_1$ ，枚举三个值即可。
对于图的情况，我们考虑cycle basis，即将整个图分解成 $r=m-n+1$ 个环。那么这时候，对于一个环，显然还是满足上面一个环的情况，而所有合法的移动方案的 $a,b$ 的差都可以看做这些环的 $k$ 的线性组合。分解的方法也很简单，找一颗mst，那么枚举非树边和树上的链就构成了一个环。
但这时候我们发现之前的证明在此处并不适用，两个环的时候的最优值的不等式就已经无法处理了。
从另外一个方式考虑。
上面我们加的边，其实和flow是完全一样的。
我们实际上可以将之前的看做flow，一个request就是(t->s)的上下界为1的流。
而我们跑一个最小费用可行流，问题就是仍然不连通，即第二步还没做。那就跑mst即可