玩样例给人新的收获

怠惰只让人坠入深渊

关于这个反向边我曾经迷惑了很久(太菜了)…也懒到一直没有手玩一下…今天突然想到了什么…就记一下好了…

我个人感觉并不像网上的主流说法是给一个反悔的机会…因为原来错误的增广路上的流量并没有减小
我想这大概像是在找增广路的时候找不到了…然后把当前节点到汇点路上已经走过的流量尽可能的迁移到别的(还能增广的)路径上

就像下面这张图
原图

不加反向边可能会变成这个样然后就不能增广了, GG

GG

加了反向边以后, 变成了这样

这样好

增广的时候从s开始, 到了节点3, 发现3原有的路径都不能增广了, 但是到2还有一条可以增广的路径, 于是到2再于是到t, 2和3的那两条路径其实相当于都没有用过(最后调整之后2和3之间的两条路径都应该是黑色的), 这样一看, 就是完美的把节点3到t阻碍增广的路径完美的移到了2到t的路径上, 简直完美QAQ

完美

By 沙茶Cansult