落絮飞雁

顺流而下,把梦做完

图论:最大流的各种变体

已知了最小费用流和最小割的性质,写写最大流的各种变体。

容量为负数时

如果将最大流转换为最小割问题时,可能会出现容量为负数的边。这种情况下时不能用最大流算法来求解的,只能通过变形避免产生负边

最小流量限制情况

如果问题同时存在下界(不仅有最大流量限制,还存在最小流量限制),需要先判断该问题是否满流。仅在满流时问题存在可行解。

判断是否满流:

将最大流出量的源点与最大流入量的汇点相连接。增加源点S和汇点T。对每条边e=(u,v)来说:

  • 从S向v连接一条容量为最小流量的边
  • 从u向T连接一条容量为最小流量的边
  • 从S向s连接一条容量为无穷的边
  • 从t向T连接一条容量为无穷的边

检查从S到T的最大流量是否为上下界流量之和,判断其是否满流。

存在多个源点(和汇点)不常用

如果存在多个源点,需要增加一个“超级源点”s和一个“超级汇点”t,从s向每一个源点连一条容量是对应最大流出容量的边。不过前提是源点和汇点之间没有对应关系

其他

除此之外,还存在无向图或顶点容量存在限制的情况。不过平时做题遇到的少,毕竟刷题太少了……之后再补充。

最大流算法主要有增广路算法和预流推进算法。其对应算法复杂度也不相同,这里介绍的是增广路算法。

感慨一句,懂算法的都是大神。

引用


原文标题:图论:最大流的各种变体|落絮飞雁的个人网站
原文链接:https://www.luoxufeiyan.com/2016/06/01/maximum-flow-problem-transform/
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。