其实这些文章好早就写好的..

我发现我一点不会网络流

设\(f(u, v)\), \(b(u, v)\), \(c(u, v)\) 为边流量 上下界

设\(g(u, v)\) = \(f(u, v) - b(u, v)\)

无源汇可行流

首先 网络流有一个流量平衡条件

也就是 \(\sum f(u, i) = \sum f(i, v)\)

对于上下界网络流

我们先给每一个边流量设为\(b(u, v)\)

会发现一个问题 就是流量平衡不满足了

解决方法如下

\(\sum f(u, i) = \sum f(i, v)\)

\(\sum (b(u, i) + g(u, i)) = \sum (b(i, v) + g(i, v))\)

设\(d(i) = \sum b(u, i) - \sum b(i, v)\)

移项 \(\sum g(i, v) = \sum g(u, i) + d(i)\)

所以若\(d(i) > 0\)则需要从\(ss\)补流

否则就要向\(tt\)流

新图跑最大流即可

若\(ss\)的新边满流则有解

有源汇可行流

原图t -> s \([0, \infty]\)

解法同无源汇可行流

此时流量为t -> s流量

有源汇最大流

先跑可行流

此时流量守恒

再在新图删掉t -> s

跑s -> t最大流

流量为两部分和

有源汇最小流

之前做法是假的

先跑可行流

然后原图t -> s 连流量为inf的边

再跑ss -> tt的最大流

上下界费用可行流

因为有下界的存在，这类费用流问题没有"最小费用最大流"之类的限制，只要是可行流就可以

同无源汇可行流

具体的话

clove_unique博客

首先建立附加源点ss和附加汇点tt

对于原图中的边x->y，若限制为[b,c]，费用为cost，那么连边x->y，流量为c-b，费用为cost

对于原图中的某一个点i，记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和

若d(i)>0，那么连边ss->i，流量为d(i)，费用为0

若d(i)<0，那么连边i->tt，流量为-d(i)，费用为0

连边t->s，流量为inf，费用为0

跑ss->tt的最小费用最大流

答案即为（求出的费用+原图中边的下界*边的费用）

总结

我会网络流了(误)

注意流量平衡以及分流逆流等操作