网络流小结②

负权环的处理。。
这是个比较蛋疼的东西。。
其实也不是很蛋疼。。
不过。。
按队长的话说。。
如果你建的图出现负环 那一般就是你建错图了 或可以避免。。
但是那是一般。。
so。。
而且处理负环的这个思想十分的重要。。
这几天我唯一没有想出来的(其他题 至少网络流的部分想出来了。。)就是这个思想。。
其实也不叫思想吧。。
网络流的性质啊。。
noi2008 志愿者招募。。
流量平衡。。
呵呵。。
呵。。
。。

好吧不蛋疼了- –
处理负环的思想就是先把负权边满流 类似上下界流处理下界 不同的是这个在流后要加反向容量
这样会有一些点不满足流量平衡 设vi = 流入点i流量-点i流出流量为

然后建一个超级源 对所有vi>0的点连边 容量为vi
建一个超级汇 对所有vi<0的点连边 容量为-vi
以超级源为源 以超级汇为汇 跑一次最大流 然后剩余网络就是满足没有负费用环的图
直接跑费用流即可
这个操作称为退流

另外退流还可以解决有上下界的网络流问题
对于一条边有上下界的边 改为只有上界 为原上界-下界
建超级源汇的操作一样
称这个新网络为附加网络

① 有源汇的上下界最大流
1.构造附加网络

     2.对ss、tt求最大流(ss、tt满流则有解)
     3.若有解,对s、t求最大流 即为ans
② 有源汇的上下界最小流
1.构造附加网络
2.加边(t, s, inf)
3.对ss、tt求最大流
4.满流即有解 解为t, s边的流量
③ 无源汇的上下界最大最小流

最大:
1.构造附加网络
2.加边(t, s, l, inf)(是有上下界的边)
3.二分l
4.用最大流是否满流判断是否有解

最小:
更最小差不多 就是把加边改成(t, s, 0, r) 然后二分r 判定

———————————–
一共A了6、7题还是多少的 题解放在下篇

网络流小结②》上有4条评论

发表评论