最小费用最大流

1、给定有向图G=（V,E），每条边e具有正整数容量，源点为s，汇点为t。假设G的最大流整数流为f。现在取E中的一条边，把它的容量增加一个单位，证明如何在O(m+n)的时间内在新容量的图中找到一个最大流。这里m是G中的边数，n是节点数。

证明：

假设把边e1增加一个单位容量，取新图的残留网络，运用广度优先搜索的办法搜索一条增广路经p（时间代价为O(m)）。若p不存在，则原图的流f即是新图的最大流；若p存在，则P经过e1。否则，原图G最大流f的残留网络也存在增广路径p，f不是最大流，产生矛盾。

对于新图中每条边e2 =（u，v），若e2属于p，则在流f中相应的边f（u，v）加1，所得到的新流f1便是新图的最大流（时间代价为O(n)）。

因为e2属于p，所以e2的残留容量>=1，而e1的残留容量为1，否则，原图G最大流的残留网络也存在增广路径p，矛盾。所以这条增广路径上的每条边只能为新流f1贡献一个单位流量。再取f1的残留网络，则e1的残留容量为0，若能找到不经过e1的增广路径p1，则原图G最大流f的残留网络也有这条增广路径，从而f不是G的最大流。所以p1经过e1，但e1的残留容量为0，没有增广路径。所以f1便是新图的最大流。所有操作总的时间代价为O(m+n)。#

 

 

 

2、证明对任意一对节点（u，v）和任意的容量函数c和流函数f，下列等式成立：C_f(u,v)+ C_f(v,u)=C(u,v)+C(v,u)

证明：C_f(u,v)+ C_f(v,u)=C(u,v)-f(u,v)+C(v,u)-f(v,u)=C(u,v)+C(v,u).#

 

3、假期医生排班问题。假设有个医院要保证每个假日至少有一个医生上班。一共有k个假期，每个要连续几天。令是包含在第j个假期的日期集合。医院共有n个医生，每个医生i有一个可以工作的假日集合。

请给出一个多项式算法确定在下面的约束下能否在每个假日都找到一个医生上班：

（1）给定参数c，每个医生应该被分配总计不超过c个假日来工作，并且只能在他/她能去工作的日期

（2）对每个假期，每个被分配工作的医生至多工作一天

 

要求算法返回一个满足这些约束的分配医生的方案，或者（正确）报告没有这样的分配方案存在。

解：构造一个有向图G：源点S出发构造n条边分别指向n个点，这n个点S1,S2,S3,……S_n代表n个医生，每条边的容量为c，代表每个医生不能工作超过c个假日。每个医生S_i出发有k条边分别指向k个点Si1 , Si2 … Sik，这k个点代表这个医生可能被分配到k个假期D1，D2，……Dk中的某一个，并且设置每条边的容量为1，代表每个医生对于某个假期最多只能工作一天。对于每个假期的每一天分别构造一个点，比如Dj假期有m个假日，分别用点Dj1，Dj2……Djm代表这m个假日，并从每个点出发构造一条有向边指向汇点T，边的容量为1，表示该假日只要有一个医生工作即可，多于的医生资源可以用于其他假日，以防医生不足。某个医生Si假设在Dj假期内有可工作的假日Djm，则构造一条边从Sij指向Djm，这条边的容量设置为1。这个图的流都是整数流，对这个图找出一个最大流f，假设f的大小<所有假日总天数，则一定不存在满足题意的分配方案。反证：假设存在满足题意的分配方案，初始化当前流f为0,若某个医生Si被分配到Dj假期的Djm假日工作，则增加如下一条路径S->Si->Sij->Djm->T到当前流f中，由假设可知遍历一遍分配方案后，得到每个假日到汇点T的有向边上容量为1的边被完全占用，因此，f已达到最大流，并且大小=所有假日总天数，矛盾，故一定不存在满足题意的分配方案。显然最大流f的大小不可能超过所有假日总天数，假设f的大小=所有假日总天数，则根据这个有向图构造时的定义可知，每个假日都至少有一个医生工作，这就构成一个分配方案，只需按照每个医生遍历一遍即可输出分配方案。

时间代价：算法的主要操作是构造一个有向图G，可在多项式时间内完成，得到图的规模是O(n+k)的，找出最大流，这个时间代价也是多项式规模的，遍历一遍图得到输出方案也是多项式时间的，故整个算法可在多项式时间内完成。#

 

 

 

 

4、下图中是一个流的剩余网络，边上标的数字是边的单位流费用。

（1）请问这个剩余网络对应的流是最小费用流吗？为什么？

（2）如果这个剩余网络中的所有边的容量都是3，如何将流的费用降低6？

  

解：

（1）不是，里面有负回路：a->c->d->b->a。费用之和为-2；

（2）在ac、cd、bd、ba边分别增加3个单位流量。