关于网络流建模的方法(一)

Posted on 2012-05-11 21:32 Mato_No1 阅读(3760) 评论(3)  编辑 收藏 引用 所属分类: 网络流
【网络流问题可以说是OI中最灵活的问题之一了,建模方法很多,但还是有一定规律的囧……当然,由于本沙茶做题暂时还比较少,可能这里总结的东东只是网络流建模技巧的一小部分,希望各位题海神犇进行补充】

网络流建模主要分为两类:直接用最大流建模、用最大流—最小割定理转化为最小割来建模。这里主要总结的是前一种。

(1)增广路思想:
应用范围较小,但是确实有一些模型用增广路思想很容易解释,用流量平衡思想却很难解释(比如下面举的例子)。
增广路思想可以概括为:原题的方案的得出可以很明显地分为一些阶段,每一阶段都会对一些变量(这些变量可能是实的也可能是虚设的)产生同样的效果值累加,而这些变量恰好有各自的限制,且互不关联。这刚好相当于网络中的一条从源点到汇点的一条增广路,对路上所有边的流量都会增加,且流量有各自限制(容量),且互不关联。并且,该模型满足下面(3)中的两条原则(可行性原则和最优性原则)。在比较多的时候,用增广路思想能够解释的模型往往是一个很明显的“物质路径”模型,某一种物质(可以是实的也可以是虚的)从源点往汇点“走”,边上的流量代表物质经过的量。
例1:[NOIP2011]观光公交
首先,由于来出发地的时间已知且一定,所以“旅行时间总和最小”其实就是所有人下车的时间总和尽可能小,因此,先求出在不用任何加速器(初始)情况下,到达每一站的时间,设为S[i],又设M[i]为在第i站上车的来的最晚的人来的时间,则很显然可以得到初始的递推式:S[i]=max{S[i-1], M[i-1]}+D[i-1](初始的D值),边界S[0]=0。
下面来看一下D[i]的减少是如何影响S值的。看下面这个例子:
N=5
i                  :  0   1   2   3   4
D[i](初始):  3   4   3   2   \
M[i]              : 1   2   6  14   \
S[i](初始):  0  4   8  11  16
现在将D[0]的值减小1之后:
i    :  0   1   2   3   4
D[i]:  2   4   3   2   \
M[i]: 1   2   6  14   \
S[i]:  0  3   7  10  16
可以发现,D[0]值减小1之后,S[1..3]的值都减小了1,而S[4]的值不变。这是因为在D[0]减小1之前,对于1<=i<3均有S[i]>M[i],D[0]若减小1,显然S[1]会减小1,而由于S[1]>M[1],S[1]=max{S[1], M[1]},所以S[1]的值减小1会使得max{S[1], M[1]}减小1,从而S[2]的值减小1,然后由于初始的S[2]>M[2],同样会使得S[3]减小1,而初始的S[3]<=M[3],故S[3]减小1不会使得max{S[3], M[3]}发生变化,所以S[4]的值不会受到影响。
所以,可以得到:D[i]减小1,会使得S[i+1..j+1]均减小1,其中j是使任意i+1<=k<=j0均满足S[k](减小前)>M[k]的最大的j0值。
从这个当中可以发现,对于原题的每一个可行方案,必然都是分为若干个阶段,其中每一阶段是将某个D[i]值减小1(当然,要满足D[i]在减小前>0),每一阶段进行后都会将从S[i+1]开始的连续的一段S值都减小1,恰好可以抽象成一条连续的路径,又因为当S[i]减小到<=M[i]的时候就必须停止了(准确来说是不能再往后延伸了),所以每个S[i]的能够继续延伸的减小的量都是有限的,为初始的S[i]-M[i](如果这个值<0,则取0),刚好是一个上限。这很明显是增广路思想。
所以,经过整理,可以建立一个网络流模型:
<1>设立两个源点s和s'(其中s是真正的源点)及汇点t,连边<s, s'>,容量为K,费用为0,表示最多只能有K个阶段;
<2>将每一站i拆成两个点i'和i'',连边<i', i''>,容量为max(S[i]-M[i], 0),费用为0,表示该点最多只能接受max(S[i]-M[i], 0)次加速器作用;
<3>对于所有的i满足1<=i<N,连边<(i-1)'', i'>,容量为INF,费用为第i站下车的人数(这是因为即使S[i]<=M[i],加速器对于本站仍然有效,只是不能继续延伸,所以表示加速器起的效果的边应该在本站的限制之前);
<4>对于所有的i满足0<=i<N-1,连边<s', i''>,容量为初始D[i],费用为0,表示使用加速器的地方,从下一站开始对S[i]起效果;
<5>对于所有的i满足1<=i<N,连边<i', t>,容量为INF,费用为0,表示加速器作用的结束。
(其实,0'和(N-1)''这两个点是木有任何意义的,可以从图中删掉)
这样,每一阶段加速器的作用都可以表示为一条从s到t的增广路,该网络流模型中的各种限制也反应了题目中的限制。对该网络求最大费用最大流,得到的总的最大费用从初始的总旅行时间中减去(注意总旅行时间是long long的),即为答案。可以证明,这个模型符合“两条原则”,所以是正确的。

(2)流量平衡思想:
这个思想的应用非常广,可以解释绝大多数网络流模型。
所谓流量平衡,就是指在一个可行流里,除了源点和汇点外,其余每个点的入边流量总和都等于出边流量总和。可以证明,一个流是可行流当且仅当其:(1)每条边的流量都不超过容量限制;(2)符合流量平衡。
流量平衡思想的主要用处是:可以把图中的每条边的流量(当然必须是非负的)都想像为一个变量的值,对于每个点,满足流量平衡,也就是一些变量的和值满足某种等量关系,如果这些等量关系刚好能够反映题目中的所有信息,边的容量限制也反映题目中的条件,且这个模型符合“两条原则”,则该模型就是正确的了。在建模的时候,应先单独考虑各个点,找到它们的所有入边和出边代表的变量是什么,然后再将这些边合并,构成图。
在用流量平衡建模时有一些技巧:
<1>要注意每条边都同时作为一个点的出边和一个点的入边,因此,每个变量必然同时关联两个等量关系,且分别出现在这两个等量关系的等号的左边和右边(或者是以一对相反数形式出现);
<2>如果题目中给出的变量和值关系不是等量关系,而是不等关系,那么可以将剩余的流量通过从源点或往汇点连边的办法,使其平衡。比如,若题目中有y1+y2>=x1+x2>=y1+y2-5这样的关系,则可以这样做:设置一个点,将y1、y2代表的边作为该点的入边,将x1、x2代表的边作为该点的出边,然后从该点往汇点连一条容量为5的边;
<3>如果点内部有限制(比如某个点自身的权值不能超过X等等),那么该点内部也“暗含”一个变量,此时就需要拆点(不一定拆成两个点,可能拆成更多的点),然后在拆出的点当中再连边,附加一些限制,然后再考虑流量平衡;
<4>如果一条边有上下界,且上下界相等(也就是该边的流量已经定死了),则可以改装成费用流,将这条边的费用设为一个绝对值很大的负数,这样就肯定能保证该边满流了。
例2:餐巾计划问题(经典问题)
这个的模型用增广路思想根本就不能解释。其实,可以用增广路思想建立一个模型,但是是错误的,可以用下面的“两条原则”检查出来。
<1>对于每天,要处理的餐巾总数=当天买的餐巾总数+当天洗好的餐巾总数+上一天保留下来的未处理的餐巾总数,这三个当作入边;
<2>对于每天,要处理的餐巾总数=送快洗部的餐巾总数+送慢洗部的餐巾总数+保存起来留到下一天处理的餐巾总数,这三个都当作出边;
<3>每天的内部有限制:要用的餐巾总数>=当天的需求量,其实,总可以构造出要用的餐巾总数=当天的需求量的最优方案,所以这些限制其实是上下界相等的。
而<1>和<2>刚好描述了每天这个整体的流量平衡,<3>是一个内部限制,用拆点解决。仔细观察所有的边可以发现,“当天洗好的餐巾总数”与“送快洗部的餐巾总数”和“送慢洗部的餐巾总数”可以合并,“上一天保留下来的未处理的餐巾总数”与“保存起来留到下一天处理的餐巾总数”也可以合并。
这样,可以构造出两种模型:
1):第i天拆成两个点i'和i'',连边<i', i''>,容量为第i天需求量,费用为0;对于任意0<=i<N-1,连边<i'', (i+1)''>,容量INF,费用0;对于任意0<=i<N,连边<S, i'>,容量INF,费用p,连边<i'', T>,容量INF,费用0;对于任意0<=i<N-m,连边<i'', (i+m)'>,容量INF,费用f;对于任意0<=i<N-n,连边<i'', (i+n)'>,容量INF,费用s;求最小费用最大流,最小的总费用就是结果;
2):第i天拆成两个点i'和i'',连边<S, i''>和<i', T>,容量均为第i天需求量,费用均为0;对于任意0<=i<N-1,连边<i'', (i+1)''>,容量INF,费用0;对于任意0<=i<N,连边<S, i'>,容量INF,费用p;对于任意0<=i<N-m,连边<i'', (i+m)'>,容量INF,费用f;对于任意0<=i<N-n,连边<i'', (i+n)'>,容量INF,费用s;求最小费用最大流,最小的总费用就是结果。
以上两种模型,看上去都符合题目中的限制,也符合流量平衡,但是,模型1)是错误的,模型2)是正确的,这是为什么呢?

(3)判定网络流模型是否正确的两个原则:
<1>可行性原则:原题中的每一种可行方案,在建立的网络流模型中都对应着一个“能求出的”流(一般是满足一定的条件的流,比如某些边必须满流等),注意这里的对应必须是“一一对应”,就是,既不能有可行方案丢失,也不能出现不可行方案;
<2>最优性原则:原题中的最优方案(准确来说是最优方案的结果),在建立的网络流模型中都对应着一个“能求出的”量(最大流量或者满足最大流量的前提下的最小费用),也就是,最优结果必须是可以通过这个模型求出的。
一个网络流模型正确,当且仅当其符合以上两条原则。
这两个原则可以检查所建立的网络流模型是否正确。比如,对于例2中的两个模型,模型1)由于最大流对应的是“买的餐巾总数尽可能多”的方案,不是最优方案,因此原题中的最优结果无法求出,显然不符合最优性原则,因此它是错误的。模型2)中,由于可行方案必然能使所有<S, i''>中的边满流,且能够求出,符合可行性原则;最优方案由于<i', T>这条边的限制,必然是最大流,且是费用最小的最大流,其最小费用为最优结果,符合最优性原则,因此它是正确的。

Feedback

# re: 关于网络流建模的方法(一)  回复  更多评论   

2014-04-17 22:29 by 武弘勋
谢谢Mato大牛,学到了很多啊。
为什么只有(一)呢(难道还有没有提到的思想吗//我太弱了求不鄙视)?
求Mato大牛继续造福OIer。

# re: 关于网络流建模的方法(一)  回复  更多评论   

2015-12-21 20:13 by TenederRun
贪心的题目竟然可以用网络流来做,挺难想到啊,佩服

# re: 关于网络流建模的方法(一)  回复  更多评论   

2015-12-21 20:57 by Mato_No1
@TenederRun
呵呵……当时没想到贪心只想到费用流建模……后来才知道竟然还有贪心做法……

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理