【题解】CF708D Incorrect Flow 网络流 — Qiuly

定义连边 $(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