已知了最小费用流和最小割的性质，写写最大流的各种变体。
容量为负数时
如果将最大流转换为最小割问题时，可能会出现容量为负数的边。这种情况下时不能用最大流算法来求解的，只能通过变形避免产生负边。
最小流量限制情况
如果问题同时存在下界（不仅有最大流量限制，还存在最小流量限制），需要先判断该问题是否满流。仅在满流时问题存在可行解。
判断是否满流：
将最大流出量的源点与最大流入量的汇点相连接。增加源点S和汇点T。对每条边e=(u,v)来说：
- 从S向v连接一条容量为最小流量的边
- 从u向T连接一条容量为最小流量的边
- 从S向s连接一条容量为无穷的边
- 从t向T连接一条容量为无穷的边
检查从S到T的最大流量是否为上下界流量之和，判断其是否满流。
存在多个源点（和汇点）不常用
如果存在多个源点，需要增加一个“超级源点”s和一个“超级汇点”t，从s向每一个源点连一条容量是对应最大流出容量的边。不过前提是源点和汇点之间没有对应关系。
其他
除此之外，还存在无向图或顶点容量存在限制的情况。不过平时做题遇到的少，毕竟刷题太少了……之后再补充。
最大流算法主要有增广路算法和预流推进算法。其对应算法复杂度也不相同，这里介绍的是增广路算法。
感慨一句，懂算法的都是大神。
引用
原文标题：图论：最大流的各种变体|落絮飞雁的个人网站
授权协议：创作共用 署名-非商业性使用 2.5 中国大陆
除注明外，本站文章均为原创；转载时请保留上述链接。