转整数流

· · 算法·理论

实数流转整数流

给定一个网络流，如果其存在一组可行流，使得每条边上的流量都是非负实数，且源点和汇点的净流量均为整数，那么总能找到这个网络流的另一组可行流，使得每条边的流量都是整数，并且每条边的新流量一定是原流量的上取整或下取整（若原本就是整数，则保持不变）。

下面我们来证明这个结论。

先把每条有向边暂时忽略方向，视为一条无向边。接着把所有已经是整数的边删掉，只保留那些当前流量不是整数的边。由于原流满足流量守恒，而源点和汇点的净流量都是整数，所以在剩下的图里，不可能出现「某个点恰好只连着一条非整数边」的情况；否则这个点的流量平衡无法由整数部分补偿回来。

因此，删完以后如果图中还剩边，那么剩下的每个连通块里都一定含有一个环。取出任意一个这样的环，并给它随便指定一个方向。

接下来考虑环上的每一条边。若某条边在原图中的方向与环方向一致，那么我们希望把它的流量向下调整；若方向相反，则希望把它的流量向上调整。更具体地说，定义这条边的「可调整量」为：

在环上取这些可调整量的最小值，记为 v。然后沿着整个环做一次调整：

这样做有两个好处。首先，由于我们在同一个环上做同幅度调整，所以环上每个点的流量守恒不会被破坏；其次，v 取的是最小可调整量，所以至少会有一条边在这次操作后变成整数。于是我们就可以把这条边删掉，继续对剩余部分重复同样的过程。

每次操作至少消去一条非整数边，因此这个过程一定会在有限步后结束，最终所有边都被调整成整数。这样，我们就构造出了所需的整数可行流，命题得证。

我们可以使用 LCT 维护这个过程。

维护一个森林，一条一条加入边，如果形成了一个环，则将这个环进行调整。时间复杂度 O(E\log V)。

分数流转整数流

现在考虑一个更特殊的情形：设存在一个常数 a，并且所有边上的流量都恰好是 \frac1a 的非负整数倍。能不能更快？

答案是可以的。

a=3

先看 a=3 的情况。此时每条非整数边的分数部分只可能是 \frac13 或 \frac23。

沿着一个环做一次调整时，每条边的变化只有两种：要么加 \frac13，要么减 \frac13。如果环的方向选得合适，就能让环上至少一半的边在这次调整后变成整数。

更具体地说，欧拉回路找环时，每次遍历到一个已经访问过的点，就把栈中对应的一段弹出，这样就能在 O(L) 的时间内取出一个长度为 L 的环，并删掉至少 \frac L2 条边。所以总复杂度是 O(E)。

a=5

当 a=5 时，单纯靠「每次消掉很多边」就不太好直接分析了，这时候可以引入势能。

设 b_1,b_2,b_3,b_4 分别表示当前图中分数部分为 \frac15,\frac25,\frac35,\frac45 的非整数边的数量，定义势能

\Phi=2b_1+3b_2+3b_3+2b_4.

现在在图中找到一个环，并沿着环的方向做一次调整。对于环上的一条边，调整只有两种可能：如果它的方向和环方向一致，就让流量加 \frac15；否则让流量减 \frac15。

看单条边的贡献变化，可以发现：

也就是说，对任意一条边，把「加 \frac15」和「减 \frac15」两种方案的势能变化量加起来，都是 -1。因此，若环长为 L，那么把环上所有边的变化量加起来，两种方案的总变化量之和就是 -L。于是至少有一种方案，能让总势能下降不少于 \frac L2。

于是总复杂度依旧是 O(E) 的。

一般的 a

让我们尝试找到一个通用的构造。

设 b_i 表示分数部分为 \frac ia 的边的数量，定义：

\Phi = \sum_{i=1}^{a-1} c_i b_i,

其中：

c_i = i(a - i).

此时 c_i 满足：

(c_{i+1}-c_i)+(c_{i-1}-c_i)=c_{i+1}+c_{i-1}=-2,

也就是对于任意一个状态 i，满足：

(\text{状态变为 } i+1 \text{ 的变化量}) + (\text{状态变为 } i-1 \text{ 的变化量}) = -2.

构造 c 的过程实际上就是构造一个二阶导数为负常数的曲线，也就是开口向下的抛物线。

于是，如果一个环有 L 条边，那么把环上所有边的两种方案累加起来，总势能变化量就是 -2L。因此，总有一种调整方向能让势能至少下降 \Omega(L)。

初始时，势能最多是 O(a^2E) 级别的，所以整个过程的总复杂度为

O(a^2E).

例题

AI 辅助了本文创作。

感谢 Cybher、the___、山田リョウ。