无源汇可行流#

将上下界的网络流转化为普通网络流。

建图:

• 添加源点 $S$ 与汇点 $T$
• 对于原图中的边 $a \to b$ 流量限制为$[c, d]$, 则连边 $a \to b$, 流量为 $d-c$
• 对于原图中的每一个点 $i$ , 记 $d(i)$ 为流入这个点的所有边的下界 $-$ 流出这个点的所有边的下界
  • 若$d(i) > 0$连 $S \to i$, 流量为 $d(i)$
  • 若$d(i) < 0$连 $i \to T$, 流量为 $-d(i)$

在新图上跑 $S \to T$ 的最大流
若新图满流则原图存在可行流
原图中边流量为新图中对应边的流量加下界。

有源汇可行流#

建图:

• 在原图中加一条 $t \to s$ 的边流量为 $[0, INF]$
• 用无源汇求解

有源汇最大流#

建图 同上

在新图上跑 $S \to T$ 最大流 记此时 $\sum{f(s, i)} = sum1$
讲 $t \to s$ 的边拆掉， 跑 $s \to t$ 的最大流
记此时 $\sum{f(s, i)} = sum2$
则答案为 $sum1+sum2$

有源汇最小流#

建图方法同无源汇可行流
求 $S \to T$ 最大流
连边 $t \to s,INF$
求 $S \to T$ 最大流
答案为 $t \to s$ 的实际流量

有源汇费用流#

将上下界的网络流转化为普通网络流。

建图:

• 添加源点 $S$ 与汇点 $T$
• 对于原图中的边 $a \to b$ 流量限制为 $[c, d]$, 费用为 $v$ , 则连边 $a \to b$ , 流量为 $d-c$ , 费用为 $v$
• 对于原图中的每一个点 $i$, 记 $d(i)$ 为流入这个点的所有边的下界 $-$ 流出这个点的所有边的下界
  • 若$d(i) > 0$连 $S \to i$, 流量为 $d(i)$, 费用为 $0$
  • 若$d(i) < 0$连 $i \to T$, 流量为 $-d(i)$, 费用为 $0$

连边 $t \to s$，流量为 $INF$，费用为 $0$

跑 $S \to T$ 的最小费用最大流
答案为 $ans+$原图中边的下界$\times$边的费用