有上下界网络流学习笔记

Author Avatar
Sakits 5月 31, 2018

无源汇可行流

  先按原图中的边连边,容量改为rlr-l
  新建源点sssstttt,设did_iii点入度下界和减出度下界和。
  若di>0d_i>0,则ssssii连边,容量为did_i,相当于预流入一些,使得ii的出边至少都能达到入边下界,保证流量平衡。
  若di<0d_i<0,则iitttt连边,容量di-d_i,相当于预流出一些,使得ii的入边至少都能达到出边下界,保证流量平衡。
  若ssss的出边满流则表示原图有可行流。

有源汇可行流

  从ttss连一条容量为[0,inf][0,inf]的边,表示sstt也需要符合流量平衡的条件,剩下的同无源汇可行流。

有源汇最大流

  先跑有源汇可行流,若ssss的出边满流则可解。
  然后断掉ttss的那条边,跑sstt的最大流即为答案。
  注意答案不需要加下界,因为流中需要加的下界已经被加进新图中算了(因为s,ts,tdid_i不为00),在有源汇可行流为了流量平衡ttss连了[0,inf][0,inf]的边,那么所有需要计算的下界都在这条边的流量中计算了。

例题

  https://vjudge.net/problem/ZOJ-3229
  https://sakits.com/CF704D