Push Relabel - 压入与重标记算法
问题
用压入与重标记算法求网络的最大流，是单源点、单汇点，边的容量都为正整数的网络。
定义
设网络中每个节点都有一个水位高度，当时边仍然可以容纳更多的流，当时称边为饱和边，不能容纳更多的流。
设节点（）的流入和流出之差为：
若相邻节点满足，称之间可以容纳额外的流。
压入操作
压入操作条件：
相邻节点的水位满足（称在的低位，在的高位）；
相邻节点的边的剩余容量满足；
压入操作：像高处的水流向最低洼的位置，对于满足压入操作条件的相邻节点，由节点流向节点，边的剩余容量更新为：
其中。任意节点能够流出的最大值为（不能凭空制造流，每个节点必须有流入才能流出），而边能够额外容纳的流为，因此实际可用的流是两者的最小值。
网络中将源点视作入流无穷大的节点，即有
将汇点视作出流无穷大的节点，即有
重标记操作
重标记操作是调整相邻节点之间的水位高度差的辅助操作，目的是尽可能将更多的流压入汇点。
重标记操作条件：
节点的流入和流出之差满足，说明该节点仍然能够制造出流；
节点存在可以容纳额外的流的邻节点（即），且水位高度之差满足；
重标记操作：
其中是所有满足重标记条件的的邻节点，将的水位设置为所有节点中最低的水位加。
解法
初始时设网络中任意两点间的流为，即（其中为相邻节点），可知任意节点的流入流出差为：
对源点进行预压入操作（无视水位）：
其中是所有与源点相邻，且满足剩余容量的邻节点。
然后设置网络中节点的水位：
遍历网络找到满足压入操作、重标记操作的相邻节点和边，并进行对应操作。重复这两种操作直到无法继续，算法结束。网络的最大流即为汇点的邻节点的出流之和：
该算法的时间复杂度为。