学习了 s e v e r a l several several天。实义数量必须markdown
因为有下界,考虑不要下界。每个弧的“可调控范围”的大小是 u p i − d o w n i up_i-down_i upi−downi,那么在我们的实际的图中,所有弧的下界都是 0 0 0,每条原图对应的弧的上界是 u p i − d o w n i up_i-down_i upi−downi。但我们要满足流量平衡,于是建立附加源SS和附加汇TT,对于每个节点,SS向它连一条容量为 ∑ d o w n x − > i \sum down_{x->i} ∑downx−>i的弧(x是所有连入i的点),它向TT连一条容量为 ∑ d o w n i − > y \sum down_{i->y} ∑downi−>y的弧(y是i所有联出的点),然后对SS->TT跑最大流。 当答案等于所有附加的弧(与SS、TT相连的弧)的容量之和时,存在可行流。
Upd on 2018.10.14 连接 T ( inf ) → S T(\inf)\rightarrow S T(inf)→S,跑上下界无源无汇可行流。
首先,标准图转无源无汇图。链接T->S容量 inf \inf inf。 然后跑上下界无源无汇可行流(可见我另一篇博文上下界网络流建模方法 无源无汇可行流 最大/最小流)。不可行就无解。 把残量留着! 然后,把T->S边拆了,接着跑S->T最大流。附加的弧已经被自动忽略了。 得到答案。 可以理解为,先跑了可行流(但是为了可行,没有流最大),再跑最大流(在可行的基础上)。
先做一个简化版:没有上下界最小流? …… 首先,强行把S和T当做平凡的点,跑上下界无源无汇可行流。注意,因为某某,SS、TT与S、T没有连边。 把残量留着! 然后,链接T->S容量为 inf \inf inf。 再,跑上下界无源无汇可行流。 答案等于T->S此时此刻的残量。 证明见各大博客。