Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

从零开始的网络流学习笔记——Dinic算法

想说的话

网络流果然听了这么多遍还是听不懂
所以只好自学
然后记录一点东西

说明

Ek算法由于太差 我不准备写了
ISAP我还没有学 现在不会
写的是Dinic算法

什么是网络流

几个要素一个不能少:
1.一个源点(就是没有入度
2.一个汇点(就是没有出度
3.有向图(水往低处走听过伐?没听过就算了反正流这种动作只能有一种方向
4.每条边都有容量(给个通俗点的解释 就是一条路最多流过多少 再多就撑爆了
所谓网络或容量网络指的是一个连通的赋权有向图 D= (V、E、C) , 其中V 是该图的顶点集,E是有向边(即弧)集,C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流,这是定义在网络上的非负函数,它一方面受到容量的限制,另一方面除去起点和终点以外,在所有中途点要求保持流入量和流出量是平衡的。(引自百度百科)

一些常用的定义

1.刚才说的源点和汇点 多数用S,T来表示
2.流量和容量
还是用刚才的水的例子来说
就是容量就是给你一根管子 里面最多流过多少水就是容量
但是流量就不一样了 这个管子不一定流满 比如说容量是2 但是只有1这么多的水
这个1就是流量
3.残量
容量-流量=残量

网络流一些性质

1.对于任意一个点 它的流量<=容量(废话
2.在流动的过程中 除S,T外 每个点的入流和出流相等
(这个东西不能贪心 进来多少就要出去多少嘛
3.
这个性质别人都说不好理解 但是我觉得很简单
对于两个点 u,v;
我们用k[i][j]表示两个点之间的流量的话
那么有k[u][v]=-k[v][u]
解释一下就是说
这个东西你选择的参照不同
从u->v流了k的水
你按照v来说 v进来了k的水 这个是从u来的
按照u来说 u出去了k的水 相当于进来了-k的水 这个可以看作是从v来的
所以性质显然成立

什么是最大流

网络流最大流就是在网络流图中给出一个方案 使得S->T的流量最大

最大流的求解

在求解之前
你需要知道增广路

增广路求解

1.找到一条从源点到汇点的路径,使得路径上任意一条边的残量>0(注意是大于而不是大于等于,这意味着这条边还可以分配流量),这条路径便称为增广路
2.找到这条路径上最小的F[u][v](我们设F[u][v]表示u->v这条边上的残量即剩余流量),下面记为flow
3.将这条路径上的每一条有向边u->v的残量减去flow,同时对于起反向边v->u的残量加上flow(为什么呢?我们下面再讲)
4.重复上述过程,直到找不出增广路,此时我们就找到了最大流

正确性

我觉得这个是显然的
我并不会一些特别正规的证法
但是我觉得就是你可以yy一下
找不到增广路的前提就是残量是0了呗
都是0了你还怎么流啊
/摊手/

求解过程详细化

举个栗子好了

相信都能看懂
最后源点的东西流不出来了
就结束了

有点小问题

我们在找增广路的时候
我们知道一定是存在最优解的
但是你怎么确定你这次找到的就是呢

SOLUTION

为了防止这种悲剧的发生
就像你犯了错事想要反悔一样
你走了错误的增广路也需要反悔
不过平时你可没有反悔的机会
但是在网络流你有
反悔的机会就是你可以把刚才流过来的东西送回去
这样相当于你什么都没做

这种反悔是这样的

比如说我们现在选择从u流向v一些流量,但是我们后面发现,如果有另外的流量从p流向v,而原来u流过来的流量可以从u->q流走,这样就可以增加总流量,其效果就相当于p->v->u->q
大概长成这个样子

图中的蓝色边就是我们首次增广时选择的流量方案,而实际上如果是橘色边的话情况会更优,那么我们可以在v->u之间连一条边容量为u->v减去的容量,那我们在增广p->v->u->q的时候就相当于走了v->u这条"边",而u->v的流量就与v->u的流量相抵消,就成了中间那幅图的样子了。
如果是v->u时的流量不能完全抵消u->v的,那就说明u还可以流一部分流量到v,再从v流出,这样也是允许的。而且这样更优

算法很好 怎么实现

第一种煞笔情况 邻接矩阵
这个很好办了 用上上面的性质三直接赋值就好了
但是之前已经有边怎么办呢了
这样在邻接矩阵中不好进行修改
面对这样的情况你有两种选择
第一种:你引进一个点P 然后u->v不变 v->u改成v->p->u把这条路用P来实现
第二种:就你邻接矩阵事多 老子不用了
改用邻接表
我们把边从0开始编号,每加入一条原图中的边u->v时,加入边v->u流量设为0,那么这时对于编号为i的边u->v,我们就可以知道i^1就是其反向边v->u

现在听起来很简单了

大体的思路我讲完了
我想这个时候大家都差不多会写了吧
别着急
你现在写的话你难道没有发现Dinic还没有出现么

让我打击你一下

刚才不是说跑增广路然后反悔么
给你个图
虽然说我们已经知道了增广路的实现,但是单纯地这样选择可能会陷入不好的境地,比如说这个经典的例子:

我们一眼可以看出最大流是999(s->v->t)+999(s->u->t),但如果程序采取了不恰当的增广策略:s->v->u->t

我们发现中间会加一条u->v的边

而下一次增广时:

若选择了s->u->v->t

然后就变成

这是个非常低效的过程,并且当图中的999变成更大的数时,这个劣势还会更加明显。
怎么办呢?

Dinic

这个时候轮到Dinic出场了

Dinic是什么

是一种非常优秀的最大流算法(废话!
Dinic算法引入了一个叫做分层图的概念。具体就是对于每一个点,我们根据从源点开始的bfs序列,为每一个点分配一个深度,然后我们进行若干遍dfs寻找增广路,每一次由u推出v必须保证v的深度必须是u的深度+1

为什么Dinic算法优秀

复杂度O(V^2E)
多路增广
• 每次不是寻找一条增广路,而是在DFS中,只要可以就递归增广下去,实际上形成了一张增广网。
当前弧优化
• 对于每一个点,都记录上一次检查到哪一条边。因为我们每次增广一定是彻底增广(即这条已经被增广过的边已经发挥出了它全部的潜力,不可能再被增广了),下一次就不必再检查它,而直接看第一个未被检查的边
这样的话优了很多

下面是Dinic的实现

1.主程序

这段很好理解了
bfs()这个函数是寻找增广路的
只要还能找到 我们就顺着这条路搜下去 给inf的流量(免得不够)
看最后用掉多少
2.bfs

这个过程是我们在给每个点赋值深度
就是深度一样的点就在一层
是一个分层的过程
最后返回的时候看一下
deep[t]代表汇点的深度
如果为-1那么证明没有被更新
这就是说没有增广路了
不然就是有增广路
这个时候就要跑dfs
3.dfs
这个是个难点

一道例题

传送门
这个题就是网络流最大流的裸题
非常ojbk Dinic无条件水过

Dinic完整代码

这是加上我上文提到的当前弧和多路增广优化的代码

6 Comments

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏