定义连边 $(u,v,(l,r),w)$ 表示连了一条 $u\rightarrow v$ 的边,流量有下界 $l$ 和上界 $r$,费用为 $w$ 。现在讨论原网络所有的边:

  • 如果 $f\leq c$:
    • 已经流了 $f$ 单位流量了,连边 $(u,v,(f,f),0)$ 。
    • 考虑退流的可能性,连边 $(v,u,(0,f),1)$ 。
    • 操作 $f$ 流 $c-f$ 单位的流量,连边 $(u,v,(0,c-f),1)$ 。
    • 继续流就需要同时调整 $c$,连边 $(u,v,(0,\infty),2)$ 。
  • 如果 $f>c$:
    • 已经流了 $f$ 单位流量了,连边 $(u,v,(f,f),0)$ 。
    • 必要的 $f-c$ 次操作,答案加上 $f-c$ 。(此处默认为调整容量)。
    • 继续流就需要同时调整 $c$,连边 $(u,v,(0,\infty),2)$ 。
    • 必要的操作不一定是调整 $c$ 而是调整 $f$,连边 $(v,u,(0,f-c),0)$ 。
    • 继续退流,连边 $(v,u,(0,c),1)$ 。

有源汇有上下界最小费用可行流即可。

代码:Submission #129722737 – Codeforces

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code