|
- UID
- 1029342
- 性别
- 男
|
—— 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。
事实上，这道题还给了我们一个很好的技巧，就是如何化不等关系为相等关系，运用这种技巧，还可以解决一般线性规划的问题。
上面两道题都很好地运用了约束条件，并通过适当的变形实现了构图，可见网络流的构图并不能依靠凭空想象，而要根据实际情况综合分析。 |
|
