转自 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了。

随机推荐

1. [BZOJ1562][NOI2009] 变换序列

   Description Input Output Sample Input 5 1 1 2 2 1 Sample Output 1 2 4 0 3 HINT 30%的数据中N≤50:60%的数据中N≤ ...

2. js和jquery如何获取图片真实的宽度和高度

   按照插入的图片的尺寸来判断图片是横图还是竖图.然后判断过后给予不同的展示方式,下面为大家介绍下js和jquery如何获取图片真实的宽度和高度   1.什么时候需要获取图片真实的宽度和高度 在做pc网页 ...

3. C标准库<signal.h>实现

   本文地址:http://www.cnblogs.com/archimedes/p/c-library-signal.html,转载请注明源地址. 背景知识 signal.h是C标准函数库中的信号处理部 ...

4. 顺序表的基本操作（C）

   在顺序存储结构实现基本操作:初始化.创建.插入.删除.查找.遍历.逆置.合并运算. 运行示例: 请输入线性表La的长度: 请输入线性表La中的元素(共5个) *** 此时线性表La中的元素 *** * ...

5. JavaScript--数组--关联(hash)数组

   关联(hash)数组的原理: hash算法: 接收一个字符串,计算出一个尽量不重复的序号 不同的字符串,计算出的序号尽量不同 相同的字符串,计算出的序号一定是相同 存入数据时: 将自定义下标名称交给h ...

6. 防止程序启动两次的方法CreateMutex()

   在工程文件中, WinMain函数里加上以下代码 HANDLE hMutex = CreateMutex(NULL, false, "Process"); if (GetLastE ...

7. poj3237--Tree 树链剖分

   题意:三种操作 ①修改第i条边的权值为val,②把u到v路径上的所有边的权值 去相反数③求u 到v路径上最大的边权 线段树的区间更新还是不熟练,,一直搞不对调试了好久还是没对,最后还是看的kuangb ...

8. CSS文字的跑马灯特效

   上学时同学有个来电带跑马灯的手机,可把我羡慕坏了,可等我买的起手机时,跑马灯不流行了,甚伤萝卜心! 今天就用CSS做个文字的跑马灯特效,缅怀一下本萝卜逝去的青春! 道具:会敲代码的巧手.七窍玲珑心.会 ...

9. c/c++ 多线程 一个线程等待某种事件发生

   多线程 一个线程等待某种事件发生 背景:某个线程在能够完成其任务之前可能需要等待另一个线程完成其任务. 例如:坐夜间列车,为了能够不坐过站, 1,整夜保持清醒,但是这样你就会非常累,不能够睡觉. 2, ...

10. java.net.ConnectException: Call From slaver1/192.168.19.128 to slaver1:8020 failed on connection exception: java.net.ConnectException: Connection refused; For more details see: http://wiki.apache.org

    1:练习spark的时候,操作大概如我读取hdfs上面的文件,然后spark懒加载以后,我读取详细信息出现如下所示的错误,错误虽然不大,我感觉有必要记录一下,因为错误的起因是对命令的不熟悉造成的,错误 ...