《有上下界网络流的初步思考》由会员分享，可在线阅读，更多相关《有上下界网络流的初步思考（6页珍藏版）》请在金锄头文库上搜索。
1、一类有上下界网络流问题的初步思考金陵中学 王立力引言：最大流类的模型在当今信息学比赛中有相当广泛的应用，本文主要讨论一类有上下界的网络流问题，通过对最大流模型，特别是附加网络的一些分析、讨论，达到抛砖引玉目的。从基本问题说起【例 1】:下图表示一个河流网,V1 是源头,V6 表示入海口 ,每段河道的通过能力(容量)如图上的各边上的数据,求单位时间内从入海口出去的流量是多少?这是一个基本的最大流问题。解决这个问题，我们只需要按照题意建立网络模型，并求一遍最大流即可。常用的最大流算法有 dinic 算法，sap 算法等。一个拓展的例子【例 2】：上面这一题中每条边的下界是 0，如果规定了上面这个网
2、络每条边的一个自然数下界，即最小的流量，那么这题应该怎么做呢？为了最终能够解决问题，不妨来看一个简化版的问题：在一个有上下界的流网络 G 中，不设源和汇，但要求任意一个点 i 都满足流量平衡条件： EviEiuff),(),(且每条边( u, v)都满足容量限制 B(u, v)f(u, v)C(u, v)的条件下，寻找一个可行流 f，或指出这样的可行流不存在。不妨称这个问题为无源汇的可行流。首先很显然的，我们可以想到，如果把所有边的下界都一定要取到，所以把它们都从上界中减去，然后再在剩下来的网络中求一个可行流。那么它是原来网络中的可行流吗？这样的转化是不对的，因为它并不满足流量守恒这一个条件。
3、为了弥补这一不足，我们可以给这个转化过的网络附加上一个源和汇。如果设： EviEiuBM),(),(即 M(i)为流入结点 i 的下界总和减去流出 i 的下界总和。如果 M(i)是正数设一附加源 S0，则可以令 C(S0, i) = M(i)。否则设一附加汇 T0，令C(i, T0) = -M(i)。如果所有从源点流出的弧和流入汇点的弧都满载，那么该网络存在一个可行流现在我们回到原问题：我们从汇点到源点添加一条上界为无穷大，下界为 a 的边，那么如果这个网络中存在可行流，则原网络中满足上下界的最大流流量=a。我们可以二分这个a，从而问题得到解决。这个方法可以很方便的拓展到费用流的情况。【例 3
4、】：变形一笔画问题在一个有向图，判断能不能一笔画访问所有的边，但有些弧上可以画多次。我们用容量 C(u,v)表示弧(u,v)最多可以重复画的次数。非常直观的问题，我们只要套用上面的模型建立流网络。每条有向边的下界是1（因为必须要画） ，上界是 C(u,v)，由于除了开始点和结束点，每个点进入次数与离开次数是相同的。因此满足流平衡条件，可以想到用流模型做。但这里每条弧都要画到，即最少要画一次。因此，成为有上下界的网络流问题。【例 4】：铁拳（ jsoi2012 第二轮）2431 51,10, +1,11,1 1,11,4给定 n 个未知数，以及 m 条方程，其中未知数系数绝对值为 1，保证等式之
5、间没有相同的单项。再给出每个未知数的范围约束。求每个未知数的取值范围。先忽略每个未知数的范围约束。假设每个选手的出道和退役时间都不是 0，那么对于每个未知数，就恰有一正一负两个单项，把每条方程看成一个点，那么一正一负就相当于流量平衡，边的流量就相当于是这个未知数的值。假如某个选手的出道时间为 0，那代表他的边就从源点出发；如果退役时间是0，那代表他的边就指向汇点。现在考虑未知数的范围约束，实际上就是对代表他的边加上上下界限制。解决了关于未知数的构图，现在再讨论方程的构图：方程中除了未知数，还有一个常数 c。如果 c0，那么它向汇点连边，容量上下界均为 c；否则源点向它连边，容量上下界均为-c。
6、由此我们成功构造出了一个上下界网络流模型，问题有解的充要条件是这个网络流存在可行流现在，我们来思考如何得出答案。由于题目所求范围不要求同时成立，我们可以对每个选手逐个击破。对于某位特定的选手，其薪金上限和下限是对称性问题，以下仅讨论上限。假如一个选手的薪金满足范围0,t，那么对于 0，他的薪金也必然满足范围0,t+。也就是说这个上限满足二分性质。我们可以二分这个边界，然后改变代表这位选手的边的上下界，按照上文方法构图，求解看是否存在可行流即可。【例 5】志愿者招募（ noi2008）申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的
7、奥运新项目招募一批短期志愿者。经过估算，这个项目需要 N 天才能完成，其中第 i 天至少需要 Ai 个人。布布通过了解得知，一共有 M 类志愿者可以招募。其中第 i 类可以从第 Si 天工作到第 Ti 天，招募费用是每人 Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最 优的招募方案。解法 1：这也是能找到的最多一种解法 举样例的例子来说明吧一共 3 天 每天需要的最少志愿者数量分别是 2 3 4有 3 类志愿者 ：第一类 可以从第 1 天到第 2 天 一个人的费用是 2第二类 可以从第 2
8、天到第 3 天 一个人的费用是 3第三类 只有第三天 一个人的费用是 4假设第 i 类志愿者的数量是 xi以上可以列为不等式：x1=2x1+x2=3x2+x3=4要求最小化目标函数 2*x1+5*x2+2*x3发现是一个线性规划问题 首先先转化为标准式(新增变量）x1-y1=2x1+x2-y2=3x2+x3-y3=4其中所有变量大于等于零 目标没变 此时在前面和后面都添加一个式子 0=0然后用第 i 个式子减去第 i+1 个式子得到 n+1 个新式子 再把常数项左移得：-x1+y1+2=0-y1-x2+y2+1=0x1-y2-x3+y3+1=0x2+x3-y3-4=0所有这些式子 左右分别相加
9、可以得到 0=0经观察可知每个变量在这些式子里都出现过两次且一正一负（因为每个志愿者时间是连续的）又因为每个式子可以看成一个流量守恒的点所以 如果一个式子有一个负系数的变量 那么就相当于是流出否则就是流入 常数项可以看做和源点或者汇点的流量然后一遍最小费用最大流解法 2：我们把每一天看做一个点，第 i 天到第 i+1 天连一条下界是需要人数，上界是无穷大，费用为 0 的边对于每种志愿者从结束天数+1，到开始天数，连一条下界是 0，上界是无穷大，费用是雇佣价格的边这样，对于图中的每一个环，都代表是招募了一个志愿者。这个图的有上下界的最小费用可行流就是我们需要的答案。这道题目得到了优美的解决。【总结】可以发现最小割问题多数情况下是求解一类最优化的问题，最大流问题多数情况下求解一类判定性的问题，而加上上下界这一条件，无疑是提高了他的约束能力。这个算法对于存在费用的情况也能够很好的进行拓展，是一个十分美丽的算法。通过在文化课中的学习，我学会了思维导图这一个学习方法。于是我为信息学竞赛中我所知道的关于网络流的模型制作了思维导图：
