Upper-Lower Bound NetworkFlow
1

2017

1

Concept 上下界网络流 顾名思义,比普通的网络流多出了下界。 考虑将下界的流量限制进行转化。将原来的边(e, v1->v2)拆边,拆出一条上界为 max-min 的边(e1),和一条上界为 min 的边(e2, 虚拟存在)。 e2 需要满足满流方才有解,但满流的同时还需要保证流量守恒(入流==出流)。故而构造虚拟源点 SS 和虚拟汇点 TT . 对于点v, 若: 下限入流等于下限出流,则两者平衡,可以认为这两个流出流入的流量都不存在。 下限入流(flowin)大于下限出流(flowout),则 SS 向 v 连一条容量为 flowin-flowout 的边,弥补不足流量。 下限入流(flowin)小于下限出流(flowout),则 v 向 TT 连一条容量为 flowout-flowin 的边,弥补过剩流量。 当且仅当 SS 的所有边都满流时有解。跑一遍 SS 到 TT 的最大流,然后验证即可。 有源汇上下界可行