网络流 - 技巧

最大流

设定一个源点，一个汇点，只有这两个点可以流量不平衡，则 $S$ 向外最大的流量就是该定义下的最大流。

使用 Dinic 算法解决，比较快的实现方式可以看下文“更快的 Dinic”。

费用流

每条边 $i$ 自带一个费用，表示顺着方向流 $1$ 则总费用加上 $p_i$ 。

有源汇最小费用流就是无源汇最小费用流，加上 $T\xrightarrow{(\infty,0)} S$ 即可。

有源汇最小费用最大流就是有源汇最小费用流， $S$ 向外的边都增加 $+\infty$ 的费用即可。

上下界流

首先我们需要超级源汇，接下来我们可以把每条边拆成三条边： $u\xrightarrow {[l,r]} v$ 变成 $S\xrightarrow l v,u\xrightarrow l T,u\xrightarrow {r-l} v$ ，然后如果原图有源汇就再连 $t\xrightarrow \infty s$ 。

对该图的超级源汇跑最大流，检查每条与超级源汇有关的边是否流满，流不满则无解。

现在我们就求出了一组可行流，它的流量是 $t\xrightarrow \infty s$ 上边的流量（注意不是 $S\to T$ 跑最大流的流量），若边带费用，则求出的是无源汇上下界最小费用流。

然后删去 $S,T,t\xrightarrow{\infty} s$ ，

有源汇上下界最大流就是可行流流量 + 残量网络上 $s$ 到 $t$ 最大流，有源汇上下界最小流就是可行流流量 - 残量网络上 $t$ 到 $s$ 最大流，有源汇上下界最小费用最大流就是最小费用流加残量网络上 $s$ 到 $t$ 最小费用最大流。

消圈

费用流消掉负环。

我们采用类似上下界的方式，对于每条负边 $w,-c$ 我们先强定其流满，即 $S\xrightarrow{w,0} v,u\xrightarrow{w,0} T$ ，答案加上 $-c$ ，然后加入 $v\xrightarrow{w,c} u$ 的反悔边，这样新图里尚且存在的边都是正权。

对这个图跑 $S\to T$ 的最小费用最大流（注意此时额外边一定流满）。

注意： $S,T$ 是超级源汇，所以这个方法可以用来跑无源汇最小费用流，而求解有源汇最小费用最大流时，如果我们不转无源汇最小费用流，就需要采用如下步骤：

$t\xrightarrow{(\infty,0)} s$ ，这是不可避免的。
跑超级源汇最大流，统计费用以及 $t\xrightarrow{(\infty,0)} s$ 的流量，作为初始费用和流量。
删除 $S,T,t\xrightarrow{(\infty,0)} s$ ，在残量网络上跑最小费用最大流。

带上下界的消圈可以使用同一组超级源汇，我们对两种图的要求都是额外边要流满。

多源汇最大流

这里的定义是 $S_i\to T_i$ ，源和汇是绑定关系。

直接 $T_i\to S_i$ 一条流量无限，费用 $-1$ 的边，然后跑无源汇最小费用流即可。

更快的 Dinic

使用结构体存下边的所有信息而不是数组，这可以提升访存优势，在餐巾计划问题加强版中可以快 10 倍。
复杂度改进：从大到小枚举二进制位，每次加入尚未加入的流量 $\ge 2^i$ 的边，可以将复杂度优化至 $nm\log C$ ，不会证，可能是假的。
- 实现上最好采用分五段加边（ $2^{24},2^{18},2^{12},2^{6},2^0$ ）。
先不加入反向边跑一遍，然后加入所有反向边跑一遍，注意不加入反向边指的是无法从另一边遍历到，反向边的边权就是残量网络上的边权，而不是当作正向边的边权或 $0$ 。

可以通过模板预流推进，注意使用 std::vector 的效率比链式前向星更高，因为我们要多次遍历。

退流

假设我们要删除 $u\to v$ ，那么我们跑 $T\to v$ 的最大流，再跑 $u\to S$ 的最大流，最后删掉 $(u,v)$ 这条边。

温馨提示，如果你的图很简单，建议通过若干次循环进行退流（枚举流向了哪里然后退掉），这对效率有极大的提升。

注意，退流后仍然需要跑 $S\to T$ 最大流。

平日里可以尝试写模板化的退流，但场上千万不要为了模板化反复思考《更好的实现方式》，采用比较好写的退流方式就好。

原始对偶费用流

类似 Johnson 全源最短路，我们使用一遍 spfa 预处理，每次使用 dijkstra 完成每次的增广。

思路是给每个点搞一个势能 $h_u=dis(S,u)$ ，然后 $w(u,v)\to w(u,v)+h_u-h_v$ ，只要我们能保证这样做之后每条边都是正的，则显然 $d'(u,v)=d(u,v)+h_u-h_v$ ，路径上的点势能抵消了。

每次跑完 dijkstra 后需要 $h_u\gets h_u+dis_u$ 。

这样做的理由：上一次跑最短路时， $dis_u+w(u,v)+h_u-h_v\ge dis_v$ ，故 $w(u,v)+(dis_u+h_u)-(dis_v+h_v)\ge 0$ ，边权非负，而新加入的反向边，一定满足其反向边在最短路上，即 $dis_u+w(u,v)+h_u-h_v=dis_v$ ，所以新边同样非负。

多项式费用流

前面忘了，中间忘了，后面忘了。

听说跑不过暴力，之后再学。