有上下界网络流地初步思考

《有上下界网络流地初步思考》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案一类有上下界网络流问题的初步思考金陵中学王立力引言：最大流类的模型在当今信息学比赛中有相当广泛的应用，本文主要讨论一类有上下界的网络流问题，通过对最大流模型，特别是附加网络的一些分析、讨论，达到抛砖引玉目的。从基本问题说起【例1】:下图表示一个河流网,V1是源头,V6表示入海口,每段河道的通过能力(容量)如图上的各边上的数据,求单位时间内从入海口出去的流量是多少?这是一个基本的最大流问题。解决这个问题，我们只需要按照题意建立网络模型，并求一遍最大流即可。常用的最大流算法有dinic算法，sap算法等。。

2、一个拓展的例子【例2】：上面这一题中每条边的下界是0，如果规定了上面这个网络每条边的一个自然数下界，即最小的流量，那么这题应该怎么做呢？为了最终能够解决问题，不妨来看一个简化版的问题：在一个有上下界的流网络G中，不设源和汇，但要求任意一个点i都满足流量平衡条件：精彩文档实用标准文案且每条边(u,v)都满足容量限制B(u,v)≤f(u,v)≤C(u,v)的条件下，寻找一个可行流f，或指出这样的可行流不存在。不妨称这个问题为无源汇的可行流。首先很显然的，我们可以想到，如果把所有边的下界都一定要取到，所以把它们都从上界中

3、减去，然后再在剩下来的网络中求一个可行流。那么它是原来网络中的可行流吗？这样的转化是不对的，因为它并不满足流量守恒这一个条件。为了弥补这一不足，我们可以给这个转化过的网络附加上一个源和汇。如果设：即M(i)为流入结点i的下界总和减去流出i的下界总和。如果M(i)是正数设一附加源S0，则可以令C’(S0,i)=M(i)。否则设一附加汇T0，令C’(i,T0)=-M(i)。如果所有从源点流出的弧和流入汇点的弧都满载，那么该网络存在一个可行流现在我们回到原问题：我们从汇点到源点添加一条上界为无穷大，下界为a的边，那么如果

4、这个网络中存在可行流，则原网络中满足上下界的最大流流量>=a。我们可以二分这个a，从而问题得到解决。这个方法可以很方便的拓展到费用流的情况。【例3】：变形一笔画问题在一个有向图，判断能不能一笔画访问所有的边，但有些弧上可以画多次。我们用容量C(u,v)表示弧(u,v)最多可以重复画的次数。精彩文档实用标准文案非常直观的问题，我们只要套用上面的模型建立流网络。每条有向边的下界是1（因为必须要画），上界是C(u,v)，由于除了开始点和结束点，每个点进入次数与离开次数是相同的。因此满足流平衡条件，可以想到用流模型做。但这

5、里每条弧都要画到，即最少要画一次。因此，成为有上下界的网络流问题。243151,10,+∞1,11,11,11,4【例4】：铁拳（jsoi2012第二轮）给定n个未知数，以及m条方程，其中未知数系数绝对值为1，保证等式之间没有相同的单项。再给出每个未知数的范围约束。求每个未知数的取值范围。先忽略每个未知数的范围约束。假设每个选手的出道和退役时间都不是0，那么对于每个未知数，就恰有一正一负两个单项，把每条方程看成一个点，那么一正一负就相当于流量平衡，边的流量就相当于是这个未知数的值。假如某个选手的出道时间为0，那代表

6、他的边就从源点出发；如果退役时间是0，那代表他的边就指向汇点。现在考虑未知数的范围约束，实际上就是对代表他的边加上上下界限制。解决了关于未知数的构图，现在再讨论方程的构图：方程中除了未知数，还有一个常数c。如果c>0，那么它向汇点连边，容量上下界均为c；否则源点向它连边，容量上下界均为-c。由此我们成功构造出了一个上下界网络流模型，问题有解的充要条件是这个网络流存在可行流现在，我们来思考如何得出答案。由于题目所求范围不要求同时成立，我们可以对每个选手逐个击破。对于某位特定的选手，其薪金上限和下限是对称性问题，以下仅

7、讨论上限。精彩文档实用标准文案假如一个选手的薪金满足范围[0,t]，那么对于Δ≥0，他的薪金也必然满足范围[0,t+Δ]。也就是说这个上限满足二分性质。我们可以二分这个边界，然后改变代表这位选手的边的上下界，按照上文方法构图，求解看是否存在可行流即可。【例5】志愿者招募（noi2008）申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N天才能完成，其中第i天至少需要Ai个人。布布通过了解得知，一共有M

8、类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天，招募费用是每人Ci元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。解法1：这也是能找到的最多一种解法举样例的例子来说明吧一共3天每天需要的最少志愿者数量分别是234有3类志愿者：第一类可以从第