自己对上下界网络流的一些理解

· · 算法·理论

由于太菜了，于是记一下:(

规定原源汇点为S,T，边的出入点为u,v,辅助源汇点为S',T' 最大流的源汇点为src,des

无源汇上下界可行流

对于b(u,v) \leq f(u,v) \leq c(u,v)的边,从u向v连一条流量为c(u,v)-b(u,v)的边

令M=\sum_{u} {In}-\sum_{u} {Out}:

若 M = 0，不加边

若 M > 0，从S'向u连一条流量为M的边

若 M < 0，从u向T'连一条流量为-M的边

若存在可行流则\sum{M[M>0]}=Maxflow( )

有源汇上下界可行流

同上的，令加入T到S流量为+\infty的边

可行流为上述附加边的流量即flow=edges[g[T].back()].flow;

有源汇上下界最大流&最小流

去掉附加边(T到S流量为+\infty的边)即

edges.pop_back(),edges.pop_back();
g[S].pop_back(),g[T].pop_back();

可行流\pm最大流(S \to T , T \to S )