最大流中反向边的作用和意义
流量需要满足三个限制条件:
- 容量限制
- 流量守恒
- 斜对称
斜对称的性质就决定了最大流中需要存在反向的流量(反向边),蒟蒻如我,不懂这样的反向流量的意义何在,于是查了一下资料,算是知道了七七八八。
反向流量的意义就在于,当增广的过程中发现当前流量并非最大流量,那么就可以通过反向的流量将原来流量退回一部分,然后得到一个更大的流量。
借用大犇的例子:
流量需要满足三个限制条件:
斜对称的性质就决定了最大流中需要存在反向的流量(反向边),蒟蒻如我,不懂这样的反向流量的意义何在,于是查了一下资料,算是知道了七七八八。
反向流量的意义就在于,当增广的过程中发现当前流量并非最大流量,那么就可以通过反向的流量将原来流量退回一部分,然后得到一个更大的流量。
借用大犇的例子: