网络流 - 技巧_LCA
JueFan 一只绝帆

网络流 - 技巧

最大流

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

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

费用流

每条边 ii 自带一个费用,表示顺着方向流 11 则总费用加上 pip_i。

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

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

上下界流

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

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

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

然后删去 S,T,t→∞sS,T,t\xrightarrow{\infty} s,

有源汇上下界最大流就是可行流流量 + 残量网络上 ss 到 tt 最大流,有源汇上下界最小流就是可行流流量 - 残量网络上 tt 到 ss 最大流,有源汇上下界最小费用最大流就是最小费用流加 残量网络上 ss 到 tt 最小费用最大流。

消圈

费用流消掉负环。

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

对这个图跑 S→TS\to T 的最小费用最大流(注意此时额外边一定流满)。

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

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

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

多源汇最大流

这里的定义是 Si→TiS_i\to T_i,源和汇是绑定关系。

直接 Ti→SiT_i\to S_i 一条流量无限,费用 −1-1 的边,然后跑无源汇最小费用流即可。

更快的 Dinic

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

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

退流

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

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

注意,退流后仍然需要跑 S→TS\to T 最大流。

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

原始对偶费用流

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

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

每次跑完 dijkstra 后需要 hu←hu+disuh_u\gets h_u+dis_u。

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

多项式费用流

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

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

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量