有上下界网络流的一些研究 王歆 ACM honoured class.

Presentation on theme: "有上下界网络流的一些研究 王歆 ACM honoured class."— Presentation transcript:

1 有上下界网络流的一些研究 王歆 ACM honoured class

2 序-网络流基础知识 假设G(V,E) 是一个有限的有向图，它的每条边(u,v)∈E都有一个非负值实数的容量c(u,v)
容量限制：f(u,v)<=c(u,v) 反对称性：f(u,v)=-f(v,u) 流守恒：Σf(u,v)=0 (u∉s,t)(v∈V) 最大流：s流出的可行流流量达到最大

3 无源汇有上下界 1 2/1 2/1 2 2/1 4 2/1 2/1 2/1 3

4 有解 1 1 2 2 1 4 1 2 3 3

5 判断有无可行流 建立附加源汇点S，T 定义每个点下界差为： 3.Di>0 新增E(i,T)上下界(0, Di)
Di<0 新增E(S,i)上下界(0,-Di) 原始边上下界改为 (0,up-low) 4.若满流则有解

6 1 2/1 2/1 1 1 1 3 2 3/2 1 1 S T

7 有源汇有上下界最大流 1.转化成无源汇 2.判断有无可行流,新建SS,TT 3.求最大流,ans=maxflow(S,T)

8 有源汇有上下界最大流 最小流？！ /0 200

9 有源汇有上下界最小流

10 有源汇有上下界最小流

11 二分或两次最大流 1、先不加后回边，消耗一定流量，若不可行，增加后回边，流S-T 2、ans=后回边流量

12 NOI2008志愿者招募 有n天，每天需要至少a[i]个志愿者，有m种志愿者，代价v[i]元从l[i]天服务到r[i]天，问最小花费。

13 志愿者招募 种类 时间 费用 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

14 对于第i个不等式，添加辅助变量Y[i] (Y[i]>=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，依次相减，得出 ① - 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

15 神一般的最小费用最大流 ① - 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 一次x[i],一次-x[i],一次y[i],一次-y[i] 所有等式右边和为0 流量平衡建图！想不到吧？

16 上下界最小费用可行流

17 例题 sgu194 判断无源汇可行流 zoj3229 有源汇最大流 sgu176 有源汇最小流

18 参考 http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html
周源 《一种简易的方法求解流量有上下界的网络 中网络流问题》