无源汇可行流
将上下界的网络流转化为普通网络流。
建图:
- 添加源点 $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$边的费用