《网络流入门》由会员分享,可在线阅读,更多相关《网络流入门(35页珍藏版)》请在金锄头文库上搜索。
1、,网络流入门,甲河到农田间有n个水站,第一个水站表示甲河,第n个水站表示农田,水站的水是从这n个水站中与之相连的另一些水站引入的(是有向的),水站与水站靠水渠连接,水渠有大有小,村民们就迷糊了,到底可以有多少水流到田里呢(即第n个水站)?,水少了庄稼长不好,就要人工撒水。(你可以将甲河看作一条储水量无限大的河,也可以将每个水站的储水量也看作无限大但是除了1号水站其他水站里开始是没有水的) 现在给你这n个水站的相连关系以及每条水渠的最大流量(注:如果给出a站b站有一条水渠,那么水只能从a流到b),问最后可以有多少水流入农田,你只要输出这个数字,村民们会判断能否满足庄稼的生长需求,你无须操心。 输
2、入格式: n,m表示n个水站 间有m条水渠。 以下m行 a,b,c 表示从a站b站有一条水渠,容量是c 输出格式:一个数字,即为最多有多少水流入农田。 Intput 6 7 1 2 10 1 3 8 3 4 8 2 4 10 2 5 6 5 6 6 4 6 10 此图中1号节点为源点,6号节点为汇点,例题1,基本概念,网络或容量网络:指的是一个连通的赋权有向图D(V、E),其中V是该图的顶点集,E是有向边(即弧)集。 网络上的流:是指定义在弧集合E上一个函数f=f(u,v),并称f(u,v)为弧(u,v)上的流量。 V中有一个源点,一个汇点,网络上的流都是由源点流出最终流入汇点。 E中的每一条
3、有向边(u,v)都有一个对应的容量上限c(u,v),通过这条边的流不能超过容量上限。,显而易见纯粹贪心是错误的,若用贪心法,会走1246 ,这样得到了10单位的水,但之后便无法运了,所以我们要换一种思路。,问题来了,既然不是每次找流量最大的,那该找哪一条咧?,残留网络,残留网络=容量网络-流量网络,Maxflow,在第一次拓展的时候,会先找到1246 这条增广路,增广后三条边的流量都达到了上限,不能再流了。,Maxflow,在第二次拓展的时候,会先找到134,此时4 6已经达到容量上限了,所以只能走4 2(这是一条反向边),再2 5 6。 这样一次次拓展,最后得到的流量和就是当前图的最大流了。
4、,Maxflow,编写程序要注意一下几个问题; 1.反向边的容量要赋为0。 2.每次找到一条增广路后,要修改路径上每条边的流量 f(u,v) +=flow; f(v,u)-=flow; 3.访问过的点不能重复访问(对于当前的拓展序列) 这样,问题就被解决了。,Maxflow,if (k!=n) m2=mind; for(j=1;j0) hashj=1; if (mindckj-fkj) mind=ckj-fkj; /*修改瓶颈*/ dg(j); if (flag) /*修改流量*/ fkj+=mind,fjk-=mind,break; mind=m2; ,SAP算法,推荐使用这种算法求最大流,
5、代码短又好理解而且效率高 将会在后面详细介绍 (其实我就会这么一种- -),最小费用最大流,最小费用最大流问题相比于最大流问题而言。对于每一条边都多了一个变量value表示单位流量的费用,保证最大流的情况下我们要使费用最少。 表面上看似乎很复杂,其实不然。 首先求出最大流肯定没有问题,那么如何保证费用最少呢,很简单:贪心。我们只要使每次找到的增广路的单位费用最小即可。 这样就把求最大流问题转变成求最短路问题了。最短路就不用讲了噻,这里推荐大家使用SPFA来写。,图5,例题2,餐巾计划问题(习题8-21) 问题描述: 一个餐厅在相继的N 天里,每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(
6、i=1,2,N)。餐厅可以购买新的餐巾,每块餐巾的费用为p分;或者把旧餐巾送到快洗部,洗一块需m天,其费用为f 分;或者送到慢洗部,洗一块需n 天(nm),其费用为sf 分。每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划,使总的花费最小。,例题2,输入: 文件第1 行有6 个正整数N,p,m,f,n,s。N 是要安排餐巾使用计划的天数;p 是每块新餐巾的费用;m 是快洗部洗一块餐巾需用天数;f 是快洗部洗一块餐巾需要的费用;n是
7、慢洗部洗一块餐巾需用天数;s是慢洗部洗一块餐巾需要的费用。 接下来的N 行是餐厅在相继的N 天里,每天需用的餐巾数。 输出: 将餐厅在相继的N 天里使用餐巾的最小总花费输出 Input.txt Output.txt 3 10 2 3 3 2 145 5 6 7,分析,对于每一天我所需要考虑的是多少送快洗部,多少送慢洗部,还有多少延期。 对于当前这一天的需求可以是新买的,可以是之前送洗刚好洗完的。 每一天的需求都要得到满足 按照这些条件,我们就可以开始构图了。,构图,割的定义,一个割(S,T)由两个点集S,T组成. S+T = V s 属于 S. t 属于 T. 提出割的定义,是为后面的证明作铺
8、垫.,最大流=最小割,证明:考虑一条增广路,上面的满流边必是容量最小的边,将这条边除去,这条增广路就无法到汇点,对每一条增广路进行这样的操作,就不会有流量流向汇点,这些删掉的边集就是最小割集,例题1,太空飞行计划问题 问题描述: W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E=E1,E2,Em,和进行这些实验需要使用的全部仪器的集合I=I1,I2,In。实验Ej需要用到的仪器是I的子集Rj。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。 W教授的任务是找出一个有效算法,确定在一次太
9、空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。,例题1,输入: 由文件input.txt提供输入数据。文件第1行有2 个正整数m和n。m是实验数,n是仪器数。接下来的m 行,每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费 用;接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。 输出: 程序运行结束时,将最佳实验方案输出到文件output.txt 中。第1 行是实验编号;第2行是仪器编号;最后一行是净收益。 input.txt output.txt 2 3 1 2 10
10、 1 2 5 6 7,例题1,把每个实验看作二分图X集合中的顶点,每个设备看作二分图Y集合中的顶点,增加源S和汇T。 1、从S向每个Xi连接一条容量为该点收入的有向边。 2、从Yi向T连接一条容量为该点支出的有向边。 3、如果一个实验i需要设备j,连接一条从Xi到Yj容量为 无穷大的有向边。 统计出所有实验的收入之和Total,求网络最大流Maxflow,最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点,也就是最后一次增广找到阻塞流时能从S访问到的顶点。,例题1,实验 设备,10,25,5,6,7,SAP算法,如果能让每次寻找增广路时的时间复杂度降下来,那么就能提
11、高算法效率了,使用距离标号的最短增广路算法就是这样的。所谓距离标号,就是某个点到汇点的最少的弧的数量(另外一种距离标号是从源点到该点的最少的弧的数量,本质上没什么区别)。设点i的标号为Di,那么如果将满足Di=Dj+1的弧(i,j)叫做允许弧,且增广时只走允许弧,那么就可以达到“怎么走都是最短路”的效果。每个点的初始标号可以在一开始用一次从汇点沿所有反向边的BFS求出,实践中可以初始设全部点的距离标号为0,问题就是如何在增广过程中维护这个距离标号。,SAP优化,1.邻接表优化: 如果顶点多的话,往往N2存不下,这时候就要存边: 存每条边的出发点,终止点和价值,然后排序一下,再记录每个出发点的位
12、置。以后要调用从出发点出发的边时候,只需要从记录的位置开始找即可(其实可以用链表)。优点是时间加快空间节省,缺点是编程复杂度将变大,所以在题目允许的情况下,建议使用邻接矩阵。 2.GAP优化: 如果一次重标号时,出现距离断层,则可以证明ST无可行流,此时则可以直接退出算法。 3.当前弧优化: 为了使每次找增广路的时间变成均摊O(V),还有一个重要的优化是对于每个点保存“当前弧”:初始时当前弧是邻接表的第一条弧;在邻接表中查找时从当前弧开始查找,找到了一条允许弧,就把这条弧设为当前弧;改变距离标号时,把当前弧重新设为邻接表的第一条弧。,SAP代码分析,总结,解决问题是一个过程,要懂得一般思考的过程 比如在解决最大流问题中,我们先想到了一种错误的贪心算法,继而改正使之成为正确的算法。 对问题要进行深度思考,所以知道怎么求最大流之后要思考如果加上费用该如何解决?,有些问题可以先从局部开始思考,然后再推演的整体 要懂得借鉴,但不要copy代码 在懂得最基础的网络流之后,此类题目最难得就是在构图方面,所以需要多做题,逐渐掌握构图的方法 希望大家能体会到思考和code的乐趣,谢谢!,