上下界网络流

上下界网络流

给你一张网络 , 对于一条边有两个限制 \(low(u,v),high(u,v)\),要求实际通过的流量为 \(low \le f(u,v) \le high\). 在此基础上满足流量守恒(流出的流量 = 流入的流量)

无源汇上下界网络流

移项可得 \(low(u,v) \le f(u,v) \le high(u,v) \Rightarrow 0 \le f(u,v) \le high(u,v) - low(u,v)\) , 每条边都变成 \(high - low\) 的形式,表示下界跑满。容易发现,按照这种做法,对于每一个节点 \(pos\),一共有 \(in = \sum_{}^{} low(u,pos)\) 的流量流入;一共有 \(out = \sum low(pos,u)\) 的流量流出。

\(out\) 和 \(in\) 的差值指示这这个点能不能遵循流量守恒。如果入流量多了,我们从虚拟源点 \(S\) 里面连一条容量为 \(in - out\) 的边到 \(pos\) , 否则连到 \(T\) 去。

跑一边最大流,如果满足流量守恒,也就是从 \(S\) 出来的权值 = \(T\) 接收到的权值,那么残量网络减少的值 + 下届就是一组解。

有源汇上下界网络流

上一篇:算法设计与分析----分治法


下一篇:查找算法