Board logo

标题: 网络流建图分析 [打印本页]

作者: yuyang911220    时间: 2016-8-20 20:04     标题: 网络流建图分析

—— R j
  网络流作为一个综合性极强的图论模型,自然是NOI的重要考点,而网络流最难的地方就是建图,这里我就简单的谈一谈我对建图的体验和方法。

首先,分析题目之后,可以对题目的模型有一个初步的判断:如果这个模型是一个很明显的基础模型,如:最大权闭合图、最大权独立集、最小权覆盖集、多进程的问题、多重匹配、最小割或者二分图的一些基本计算等,都是可以很轻松地通过一些构图技巧实现建图。
如果题目要求的不是这些基础模型,那就需要进行更深层次的分析。

据我总结,针对这样的题目,构图大概可以分为三步:

1.分析题目约束条件,写出恰当的表达式。
2.适当变形以使其满足网络流的性质。*
3.根据约束条件构图。

*关于网络流的性质,详情参见胡伯涛《最小割》。

以下我举两个例子来进行讨论:

1.餐巾问题
题目简述:
一个餐厅在相继的N 天里, 每天需用的餐巾数不尽相同。 假设第i天需要ri块餐巾(i=1,
2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为p分;或者把旧餐巾送到快洗部,
洗一块需 m天,其费用为 f 分;或者送到慢洗部,洗一块需 n 天(n>m),其费用为s<f 分。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多
少块保存起来延期送洗。 但是每天洗好的餐巾和购买的新餐巾数之和, 要满足当天的需求量。
试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划,使总的花费最小。

解析:
乍看来,不是我们的基本模型,因此,先分析约束条件

able表示第i天可用的餐巾数,buy表示第i天购买的餐巾数,used表示第i天的脏餐巾数,today表示第i天的需求,yesterday表示第i天的前一天送过来的脏餐巾数。


able=buy+wash;          ①
used=today+yesterday;    ②
able=today;               ③

合并①③   buy+wash= today; ④
如果将每一天的可用的餐巾看做一个集合b,每一天的脏餐巾看做一个集合a,②式就反应了i.a的流
量情况,每天的脏餐巾是今天剩下的和昨天剩下的和起来;④式就反应了i.b的流量情况,即每一天可用的来源于购买的和洗干净的餐巾;这事实上是一种流量守恒,可用来构建网络流图。然后是洗餐巾的问题,一块餐巾洗后就成了一块可用的餐巾,等效于重新买了一张,只是费用不同,数量也有限制罢了。
因此我们可以如此建图:
建立附加源S汇T。

1、从S向每个I.a连一条容量为ri,费用为0的有向边。
2、从每个I.b向T连一条容量为ri,费用为0的有向边。
3、从S向每个I.b连一条容量为无穷大,费用为p的有向边。
4、从每个I.a向(I+1).a(i+1<=N)连一条容量为无穷大,费用为0的有向边。
5、从每个I.a向(I+m).b(i+m<=N)连一条容量为无穷大,费用为f的有向边。
6、从每个I.a向(I+n).b(i+n<=N)连一条容量为无穷大,费用为s的有向边。

求网络最小费用最大流,费用流值就是要求的最小总花费。
网络最大流满足了问题的约束条件(因为在这个图上最大流一定可以使与T连接的边全部满流,其他边只要有可行流就满足条件),而且还可以保证总费用最小,就是我们的优化目标。


2.志愿者招募(NOI2008)
题目简述:
  N天内,第i 天至少需要Ai 个人,一共有M类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci元。每类志愿者的数量都是无限多的。求满足要求的费用最少的方案。

解析:
  例如一共需要4天,四天需要的人数依次是4,2,5,3。有5类志愿者,如下表所示:
种类 1 2 3 4 5
时间 1-2 1-1 2-3 3-3 3-4
费用 3 4 3 5 6
设雇佣第i类志愿者的人数为X,每个志愿者的费用为V,第j天雇佣的人数为P[j],则每天的雇佣人数应满足一个不等式,如上表所述,可以列出
P[1] = X[1] + X[2] >= 4
P[2] = X[1] + X[3] >= 2
P[3] = X[3] + X[4] +X[5] >= 5
P[4] = X[5] >= 3
对于第i个不等式,添加辅助变量Y (Y>=0) ,可以使其变为等式
P[1] = X[1] + X[2] – Y[1] = 4
P[2] = X[1] + X[3] – Y[2] = 2
P[3] = X[3] + X[4] +X[5] – Y[3] = 5
P[4] = X[5] – Y[4] = 3
在上述四个等式上下添加P[0]=0,P[5]=0,每次用下边的式子减去上边的式子,得出
① P[1] – P[0] = X[1] + X[2] – Y[1] = 4
② P[2] – P[1] = X[3] – X[2] -Y[2] +Y[1] = -2
③ P[3] – P[2] = X[4] + X[5] – X[1] – Y[3] + Y[2] =3
④ P[4] – P[3] = – X[3] – X[4] + Y[3] – Y[4] = -2
⑤ P[5] – P[4] = – X[5] + Y[4] = -3

我们将最后的五个等式进一步变形,得出以下结果
① – X[1] – X[2] + Y[1] + 4 = 0
② – X[3] + X[2] + Y[2] – Y[1] – 2 = 0
③ – X[4] – X[5] + X[1] + Y[3] – Y[2] + 3 = 0
④ X[3] + X[4] – Y[3] + Y[4] – 2 = 0
⑤ X[5] – Y[4] – 3 = 0

可以发现,每个等式左边都是几个变量和一个常数相加减,右边都为0,恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量,负的变量相当于流出该顶点的流量,而正常数可以看作来自附加源点的流量,负的常数是流向附加汇点的流量。因此可以据此构造网络,求出从附加源到附加汇的网络最大流,即可满足所有等式。而我们还要求最小,所以要在X变量相对应的边上加上权值,然后求最小费用最大流。

接下来,根据上面五个等式构图。

每个等式为图中一个顶点,添加源点S和汇点T。
如果一个等式的常数项为正整数c,从源点S向该等式对应的顶点连接一条容量为c,权值为0的有向边;如果一个等式的常数项为负整数c,从该等式对应的顶点向汇点T连接一条容量为c,权值为0的有向边。
如果一个变量X在第j个等式中出现为-X,在第k个等式中出现为X,从顶点j向顶点k连接一条容量为∞,权值为V的有向边。
如果一个变量Y在第j个等式中出现为-Y,在第k个等式中出现为Y,从顶点j向顶点k连接一条容量为∞,权值为0的有向边。
构图以后,求从源点S到汇点T的最小费用最大流,费用值就是结果。
根据上面的例子可以构造出如下网络,红色的边为每个变量X代表的边,蓝色的边为每个变量Y代表的边,边的容量和权值标已经标出(蓝色没有标记,因为都是容量∞,权值0)。

在这个图中求最小费用最大流,流量网络如下图,每个红色边的流量就是对应的变量X的值。

所以,答案为4*3+2*3+3*6=36。

事实上,这道题还给了我们一个很好的技巧,就是如何化不等关系为相等关系,运用这种技巧,还可以解决一般线性规划的问题。

上面两道题都很好地运用了约束条件,并通过适当的变形实现了构图,可见网络流的构图并不能依靠凭空想象,而要根据实际情况综合分析。
作者: yuchengze    时间: 2016-8-21 12:20

好文章,受教了




欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0