# 最大流问题

## 定义

${\displaystyle N=(V,E)}$为一个网络，其中${\displaystyle s}$${\displaystyle t}$分别是${\displaystyle N}$的源点和汇点（${\displaystyle s,t\in V}$）。

1. 对于每个${\displaystyle (u,v)\in E}$，有${\displaystyle f_{uv}\leq c_{uv}}$（即容量限制：一个边的流量不能超过它的容量）；
2. 对于每个${\displaystyle v\in V\setminus \{s,t\}}$，有${\displaystyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}}$（即流的保留：流入一个节点的流的总和必须等于流出这个节点的流的总和，源点和汇点除外）。

## 解法

MPM (Malhotra, Pramodh-Kumar and Maheshwari)算法[8] O(V3) 只适用于无环图。参考 Original Paper.
Dinic算法 O(VE log(V))
push-relabel maximum flow算法 O(V2E)
Push-relabel算法，使用FIFO vertex selection rule O(V3)
Push-relabel算法，使用 dynamic trees ${\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}$
KRT (King, Rao, Tarjan)算法[9] ${\displaystyle O(EV\log _{\frac {E}{V\log V}}V)}$
Binary阻塞流算法[10] ${\displaystyle O\left(E\cdot \min(V^{\frac {2}{3}},{\sqrt {E}})\cdot \log {\frac {V^{2}}{E}}\log {U}\right)}$
James B Orlin's + KRT (King, Rao, Tarjan)算法[11] ${\displaystyle O(VE)}$ Orlin's algorithm页面存档备份，存于互联网档案馆） solves max-flow in O(VE) time for ${\displaystyle E\leq O(V^{{16 \over 15}-\epsilon })}$ while KRT solves it in O(VE) for ${\displaystyle E>V^{1+\epsilon }}$.

## 参考文献

1. ^ Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259.
2. ^ Gass, Saul I.; Assad, Arjang A. Mathematical, algorithmic and professional developments of operations research from 1951 to 1956. An Annotated Timeline of Operations Research. International Series in Operations Research & Management Science 75. 2005: 79–110. ISBN 1-4020-8116-2. doi:10.1007/0-387-25837-X_5.
3. ^ Harris, T. E.; Ross, F. S. Fundamentals of a Method for Evaluating Rail Net Capacities (PDF). Research Memorandum (Rand Corporation). 1955 [2017-03-07]. （原始内容存档 (PDF)于2017-02-17）.
4. ^ Ford, L. R.; Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8: 399. doi:10.4153/CJM-1956-045-5.
5. ^ Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
6. ^ Kelner, J. A.; Lee, Y. T.; Orecchia, L.; Sidford, A. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF). 2014: 217. ISBN 978-1-61197-338-9. . doi:10.1137/1.9781611973402.16. （原始内容 (PDF)存档于2016-03-03）.
7. ^ Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem. MIT News. 7 January 2014 [8 January 2014]. （原始内容存档于2014-02-26）.
8. ^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. An ${\displaystyle O(|V|^{3})}$ algorithm for finding maximum flows in networks. Information Processing Letters. 1978, 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
9. ^ King, V.; Rao, S.; Tarjan, R. A Faster Deterministic Maximum Flow Algorithm. Journal of Algorithms. 1994, 17 (3): 447–474. doi:10.1006/jagm.1994.1044.
10. ^ Goldberg, A. V.; Rao, S. Beyond the flow decomposition barrier. ACM期刊. 1998, 45 (5): 783. doi:10.1145/290179.290181.
11. ^ Orlin, James B. Max flows in O(nm) time, or better. STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013: 765–774. doi:10.1145/2488608.2488705.