转自 Because of you 的总结

上下界网络流的问题严格的分，可以分为四类吧。

1：无源汇可行流 sgu 194

2：有源汇可行流 poj 2396 这题比较好，我建图建了将近200行

3：有源汇最大流 zoj 3496 这题比较劲爆，需要两次二分

4：有源汇最小流 hdu 3157 sgu 176

下面三种都是先转换成无源汇的来做，所以重点讲无源汇的网络流怎么做。上面两篇链接里的我就不再赘述了。

假设一条边的上界流为R 下界流为L，则 R-L为自由流，意思就是只要流了L，接下来要流多少随便。

无源汇的上下界可行流是指一种方案。流是循环在流的，每个点都满足流入等于流出。我们再细分一下就是sigma(进来的下界流) + sigma(进来的自由流) = sigma(出去的下界流)+sigma(出去的自由流)

假设我们要将这个网络流问题转换成普通的最大流问题，那么首先就是要把下界去掉，即下界为0。去掉后要把下界的因素叠加在原图中，怎么叠加呢？假设一个点进来的下界流总和减去出去的下界流总和为M，如果M为正，表示进来的自由流要比出去的自由流少 M ，所以我们人为的向这个点补充进M（想想为什么）。如果M为负，也是类似的，从当前点额外地流出去M。补充进流量和流出去需要建一个源点，一个汇点。

为什么这样子建好图求最大流后如果源点流出的边满流就有解？

想想看，如果源点流出的边都能满流，意味着什么？？我们可以把中间的网络看成一个黑箱，源点是入口，汇点是出口，不管中间是循环的流也好，或者是直接经过一条链到达汇点也好，我们不关心，我们关心的只是进去的流能否流出来，其实也就是黑箱里的网络能否支持流进来的流。如果能够支持，说明原网络能够支持这么些必须要流的自由流。也就意味着原网络存在一个方案喽！

有源汇上下界的最大流的做法是：由汇点T向源点S建边（上界为INF，下界为0），（这一步非常犀利，等一下解释为啥么犀利），转换成无源汇的网络流问题，用上面的方法判断是否有解，如果有解的话，再跑一次源点S到汇点T的最大流，现在的最大流就是答案啦。。。

刚才那一步犀利犀利在只建了一条边就将原图转换成另一个已经可以解决的问题了（也许你不感觉犀利，但从无到有的想出这个方法在本菜看来实在犀利）

第一次跑完最大流的时候其实就可以求解网络中的一个可行流的流量了，这个流量其实就是最后加进去的那条边的反向流。因为加进去的时候下界是为0的，因此显然是正确的。

为什么最后再跑一遍最大流就能求得答案？

因为第一遍跑的是可行流，可能还有些边有余力可以再流一流，所以再跑一遍，原来那个可行流的流量记录在了T ->S的反向流中，因次这个流再流一次就流回去了，所以再留一次就是答案！

好了，既然有下界，那肯定也可以求最小流。

先在原图中跑一遍最大流，然后连上T-> S (0,INF) 的边，再跑一遍

关于为什么第一遍跑的时候那个流量可能不是最小流，开头第一篇博客中已经有讲为什么了（环）

例题：poj 2396。

题意：有一个矩阵，告诉你每行的和以及每列的和，还有一些限制，综合起来其实就是告诉你某个数a[i][j]的范围，不过要自己去求。最后问你是否存在这样一个矩阵，有的话输出。

想仔细一点就可以看出这是个很裸的上下界流，但要先拆点，1~n*m表示矩阵中的点，n*m+1~到2*n*m表示拆成的点，2*n*m+1~2*n*m+m表示每一行，2*n*m+m+1~2*n*m+m+n表示每一列，那每行的和每列的和可以通过新建源点，汇点来限制了，这些边的上下界都是一个定值，其余的就比较简单了，套个有源汇的上下界最大流就ok了。

巴特西

转自 Because of you 的总结

最新文章

热门文章