有上下界网络流的初步思考.docVIP

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