RainAir
My OI Blog
RainAir
Dinic 学习笔记
Dinic 学习笔记

Dinic 是一种网络最大流的算法。

引入

网络流的本质是线性规划。
定义:有向图 $(V,E)$ 存在源点 $S \in V$ 和汇点 $T \in V,S \neq T$,每条边都有一个容量 $c$。

对于任意一个时刻,设 $flow(u,v)$ 表示实际流量,则整个图 $G$ 的流网络满足如下性质:
1. 容量限制:$\forall u,v $,$flow(u,v) < c(u,v)$
2. 反对称性: $\forall u,v $,存在 $ flow(u,v) = -flow(v,u) $
3. 流量平衡, $\forall u,u \neq S,u \neq T$,应满足 $\sum flow(u,v) = 0$,即每个点不会制造或消耗流量。
可行流:在容量网络 G 中满足以下条件的网络流 flow ,称为可行流.
1. 弧流量限制条件: $0 \leq flow(u,v) \leq c(u,v)$
2. 平衡条件: 即流入一个点的流量要等于流出这个点的流量(源点和汇点除外).
零流:如果网络流上每条弧的流量都为 $0$ ,则该网络流成为零流。
伪流:如果一个网络流只满足弧流量限制条件,不满足平衡条件,则这种网络流为伪流,或称为容量可行流.(预流推进算法有用)
在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.
残余流量:可以感性理解为 $cl(u,v) = c(u,v) – flow(u,v)$
残余网络:在一个网络流图上,找到一条源到汇的路径后,对路径上所有的边,其容量都减去此次找到的量,对路径上所有的边,都添加一条反向边,其容量也等于此次找到的流量,这样得到的新图,就称为原图的残余网络。
上面讲了一些基本的定义,看完下面的内容已经足够了。

Dinic

增广路找最大流

首先注意一个性质:如果一个可行流不是最大流,那么当前网络中一定存在一条增广路。(作者也不会证明)
增广路大家在学习二分图的时候一定都听说过了。
大概找增广路的过程就是 dfs 一遍,判断这条边残量是否大于 $0$,如果大于 $0$ 就通过这条边进行增广。
详细说一下找增广路的过程:
1. 找到一条从源点到汇点的路径,使得路径上每一条边的残留都 $>0$,这条路径叫做增广路;
2. 找到这条路径上最小的残量,记为 $f$;
3. 将这条路径上每一条有向边的残量减去 $f$,同时对于反向边的残量加上 $f$;
4. 重复直到找不到增广路。

为什么要建反向边

因为你在寻找增广路的时候,在前面找到的不一定是一个最优解,如果我们建一个流量相反的边,那么就代表可以从这条反向边流过而实现反悔。
https://blog.aor.sd.cn/wp-content/uploads/2018/11/o_WLL-2.png

反向边的实现

因为你是一个指针选手,对于每个边都建一个指向其反向边的指针就可以了。

上述朴素算法太慢了

可以被一些奇妙的极限数据卡掉,大概就是有很大和很小的边权,如果增广策略不对,就会陷入增广许多次的情景,时间复杂度飞天。
例如下面这组数据:
https://blog.aor.sd.cn/wp-content/uploads/2018/11/o_WLL-3-1.png
手动模拟一下就会发现它要循环许多遍!这是我们不可以接受的。
于是 Dinic 算法解决了这个问题。

Dinic 算法

Dinic 算法引入一个分层图的概念(不是分层图最短路),对于每一个节点记录一个 $level$ 表示到达源点的距离(边权看作 $1$ )。我们限制每次由 $u$ 增广出来的 $v$ 必须满足 $level_u + 1 = level_v$。这样就能防止上述的奇怪情况卡掉朴素算法。
Dinic 算法的时间复杂度理论上界是 $O(n^2m)$,但是绝大多数情况都跑不满。

当前弧优化

即每一次dfs增广时不从第一条边开始,而是记录点u之前循环到了哪一条边,以此来加速。
这样能快不少,更不容易跑到上界了

具体实现

结构体定义

我们定义点结构体(Node)和边结构体(Edge)

剩下的操作在代码里会给出注释。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/288
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

Dinic 学习笔记
Dinic 是一种网络最大流的算法。 引入 网络流的本质是线性规划。 定义:有向图 $(V,E)$ 存在源点 $S \in V$ 和汇点 $T \in V,S \neq T$,每条边都有一个容量 $c$。 对于任意一个时刻…
扫描二维码继续阅读
2018-11-22
标签
近期评论