huidong

首页 | 会员登录 | 关于争取 2022 寒假做出汇东网 Ver3.0.0 !
搜索文章


# Part 1 什么是网络流


## 1.概念


网络可以理解为**一堆水管**,而流则可以理解为**水流**。水流可以**从源头源源不断地**流进管道系统,然后从**排水口流出管道系统**。


但因为**水管是有大小的**,如果单位时间流过的水比这跟水管的容量还大,那么这跟水管就会被撑爆。所以,**单位时间内每根水管能流的水量是有限的**,我们**把第 $i$ 根水管的容量记为 $c_i$**,表示第 $i$ 根水管在单位时间内最多能流 $c_i$ 那么多的水。


而且由于水往低处流,所以**水管是有方向的**。


管道系统肯定不止一根水管,而多根水管连起来就需要一些**节点**。我们可以把节点理解为**水流中继站**,因为水流中继站肯定不会把水给吞了,所以**流入某个中继站的水流总量和流出这个中继站的水流总量是相等的**。


把这个水管系统画出来大概就是这样的:(`S` 表示源头,`T` 表示排水口,箭头表示水管,箭头旁边的数字表示水管的容量)


![](https://cdn.luogu.com.cn/upload/image_hosting/ai2oguz8.png)


在上图中,我们发现其实**源头和排水口也可以当成中继站来用**。


这种图是不是很眼熟?没错!这是一个**带权有向图**,水管在图里是**边**,水管的容量是**边权**,中继站是**节点**,源头和排水口也是**节点**。


## 2.术语


因为像 `水管容量`、`排水口出水量`、`水管系统` 这类名字众 `Oier` 不喜欢,所以大家给它们取了一些~~听起来很高级~~学术化的名字。


大家把 `水管` 叫做**边**,`水管容量` 叫做**边的容量**,`排水口出水量` 叫做**流量**,`水管系统` 叫做**网络**,`源头` 叫做**源点**,`排水口` 叫做**汇点**,`中继站` 叫做节点。


也就是


```cpp

#define 边 水管

#define 边的容量 水管容量

#define 流量 排水口出水量

#define 网络 水管系统

#define 源点 源头

#define 汇点 排水口

#define 节点 中继站

```


# Part 2 网络最大流问题


## 1.定义


顾名思义,“网络最大流” 即**一个网络在单位时间内最多能流多少流量**。而网络最大流问题即**给你一个网络和源点、汇点编号,要你求这个网络的最大流**。


举个例子,对于下图中的网络,它的最大流便为 `10`。


![](https://cdn.luogu.com.cn/upload/image_hosting/ai2oguz8.png)


## 2.求解


如何用算法求解网络最大流呢?


考虑最~~暴力~~朴素的做法,很显然可以爆搜,但时间复杂度会爆炸的。


现在有请我们的嘉宾——猴子,来帮忙求解网络最大流。


- ### 反向边的引入


我们给猴子一个这样的网络(**边上的数表示这条还有多少容量**)


![](https://cdn.luogu.com.cn/upload/image_hosting/1m761p8v.png)


猴子很开心,因为它一眼就看见了一条可以让流 `1` 流量的路


![](https://cdn.luogu.com.cn/upload/image_hosting/obnb6ilz.png)


现在这个网络的最大流从原来的 `0` 更新成了 `1`。


猴子尝试继续找路,可它发现找不到路了,于是猴子跑路了。


`Oier` 们又来搞事情了,大家觉得 `路` 不好听,所以把猴子找的这种路叫做**增广路**。


那么猴子求出来的是最大流吗?**不**,很明显可以**让上面的两条边通过 `1` 的流量,再让下面的两条边通过 `1` 的流量**,整个网络的最大流其实是 `2` 而不是 `1`。


猴子被友好的工作人员请回来了,现在它开始反思,为什么它会错呢?`114514` 秒过去了,猴子终于知道自己错误的原因了,那就是它**不会反悔**。如果能不经过中间那条边它求的最大流就会变成 `2` 了。


猴子跑去吃香蕉了,我们又要自己思考做法了。


吸取了猴子惨痛的失败经验后,我们发现,电脑其实也像一只猴子,它并不会反悔。那如何教会电脑反悔呢?**建反向边就行啦!**


不过要注意,**反向边的容量一开始是 `0`**。


例如我们之前给猴子的网络,建完反向边之后就变成这样了


![](https://cdn.luogu.com.cn/upload/image_hosting/ppddfojx.png)


反向边如何使用呢?很简单,**当一条边流过 $k$ 的流量时,反向边便增加 $k$ 的容量;当一条边的反向边流过 $k$ 的流量时,它的正向边便增加 $k$ 的容量**。这样相当于给了电脑一个反悔的机会,**如果这条边流过去了 $k$ 的流量,那么它的反向边流 $k$ 的流量就相当于把流走的流量还给流量流出去的节点**。


增加反向边后,猴子就会发现它能轻松地求出网络最大流了。


首先,猴子还是找到了之前那一条增广路。不过这次它把反向边的容量增加了


![](https://cdn.luogu.com.cn/upload/image_hosting/j7vf9u6l.png)


现在猴子发现它还能找增广路


![](https://cdn.luogu.com.cn/upload/image_hosting/r0ahn8k5.png)


这下它总算求出了正确答案,猴子开心地跑了。


我们发现,猴子**在找第二条增广路的时候走了中间那条边的反向边**。这其实表示猴子反悔了,**它让红色那条增广路不走中间那条边,改成走右下那一条,而当前的增广路 “接管” 了之前红色增广路走的边**。


- ### EK 算法


有了反向边,电脑也可以轻松地求网络最大流了。


建完图后,我们可以**用 `bfs` 来找增广路**。根据网络最大流的定义,**`bfs` 应该从源点开始,到汇点结束**。所以如果 `bfs` 时访问到了汇点,那么电脑就找到了一条增广路。


找到增广路之后**还得把增广路上的正向边的剩余容量减少,把反向边的剩余容量增加**。所以我们需要一个数组 `pre`,$pre_i$ 表示**在当前找到的增广路中,$i$ 是从哪一条边过来的**。


特别的,反向边的存储有个特殊方式,那就是 $i$ **的反向边编号为 $i$ $xor$ $1$,写成代码就是 `x^1`**。这么规定是因为电脑很笨,它**在更新剩余容量的时候不知道哪一条是正向边,哪一条是反向边,所以我们需要 $xor$ 这种对称(雾)的操作**。


例如: `2` 号边的反向边就是 `2^1=3`,而 `3` 号边的反向边就是 `3^1=2`。


问题又来了,`1^1=0`,因为我们不喜欢 `0` 这个数字,所以**边的编号应该从 `2` 开始,也就是一开始 `esum=1`(`esum` 表示当前边的条数)**。


由于**一个网络可能不止一条增广路**,所以我们需要**跑很多次 `bfs`,一直跑到找不到增广路为止**。


**这种利用很多次 `bfs` 来求网络最大流的算法被称为 `EK 算法`**


附上 EK 算法的代码:


```cpp

// P3376 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>


using namespace std;


typedef long long ll;


int n,m,s,t;

int esum,to[10005],head[205],nxt[10005];

ll ans,c[10005],f[10005];

int las[205];

bool vis[205];


inline void init()

{

esum=1;

memset(head,-1,sizeof(head));

}


inline void add(int x,int y,ll w)

{

c[++esum]=w;

to[esum]=y;

nxt[esum]=head[x];

head[x]=esum;

}


inline bool bfs()

{

queue<int> q;

q.push(s);

memset(vis,0,sizeof(vis));

vis[s]=true;

f[s]=1e17;

while(!q.empty())

{

int u=q.front();

q.pop();

for(int i=head[u];i!=-1;i=nxt[i])

{

int v=to[i];

if(c[i]>0&&!vis[v])

{

las[v]=i;

f[v]=min(f[u],c[i]);

vis[v]=true;

q.push(v);

if(v==t)

{

return true;

}

}

}

}

return false;

}


inline ll upd()

{

ll nflow=0;

nflow+=f[t];

int u=t;

while(u!=s)

{

int i=las[u];

c[i]-=f[t];

c[i^1]+=f[t];

u=to[i^1];

}

return nflow;

}


inline ll ek()

{

ll maxflow=0;

while(bfs())

{

maxflow+=upd();

}

return maxflow;

}


int main()

{

scanf("%d%d%d%d",&n,&m,&s,&t);

   init();

for(int i=1;i<=m;i++)

{

int x,y;

ll w;

scanf("%d%d%lld",&x,&y,&w);

add(x,y,w);

add(y,x,0);

}

printf("%lld\n",ek());

return 0;

}

```


- ### dinic 算法


在 EK 算法中,我们需要跑很多次 `bfs` 才能得到答案。但 `bfs` 在最坏情况下是要访问所有节点的,这导致 **EK 算法的时间复杂度并不够优秀**。所以,人们发明了 dinic 算法。


dinic 算法是一种十分巧妙的算法,它利用了**层次图**来减少 `bfs`执行的次数。


- #### 层次图


层次图,顾名思义,就是把图分层。可以这么理解:一张图本来是平的,现在有个人把它放在了山坡上,它就斜过来了。由于水往低处流,所以把一个网络分层之后,**水流(流)就只能从高处(深度小)的节点流向低处(深度大)的节点,而分层的过程其实就是一次 `bfs`**。


分层的流程大概如下:首先把源点的深度设置成 `1`,然后访问和源点相连的其它点,把它们的深度设置成 `2`,依此类推。


- #### 算法流程


首先我们需要把网络分层,然后对于分完层的网络,我们再跑很多遍 `dfs`。但是**在 `dfs`里我们只允许当前节点的流向深度正好比当前节点深度大 `1` 的节点流去**。这样保证了 dinic 算法的正确性,**其实也可以理解为用 `dfs` 来跑 EK 算法中的 `bfs`**。但是用 `dfs` 有个好处,那就是 **`bfs` 需要遍历完整个图才能找到一条增广路,而 `dfs` 遍历整个图有可能会找到多条增广路。**


**如果 `dfs` 到达不了汇点了(找不到增广路了),那么就需要重新分层,再跑一次 `bfs`。如果 `bfs` 到达不了汇点,那么就说明增广路找完了,求出了网络最大流**。


写成伪代码大概是这样的:


`dfs` 部分:


```

dfs(int u,int w) // u 表示当前节点的编号,w 表示流向当前点的流量

{

遍历所有从 u 出发的边 i

{

int v=i 到达的节点;

if(v 的深度 == u 的深度 +1)

{

int re=dfs(v,min(w,i 的容量));

if(增广成功)

{

更新正向边和反向边的容量;

return re;

}

}

}

return 增广失败;

}

```


求解部分:


```

while(bfs 可以到达 汇点)

{

while(增广路增广的流量 = dfs(s,inf) != 增广失败)

{

网络最大流+=增广路增广的流量;

}

}

```


此外,dinic 算法还有两个优化,分别是**多路增广优化**和**当前弧优化**。多路增广优化**就是令一次 `dfs` 能够找到多条增广路**,而当前弧优化就是**令 `dfs` 不再增广增广过的边**。


附上没加优化的代码和加了这两个优化的代码:


没加优化的:


```cpp

// P3376

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>


using namespace std;


typedef long long ll;


int n,m,s,t;

int esum,to[10005],nxt[10005],h[205];

ll c[10005];

int dep[205];


inline void init()

{

esum=1;

memset(h,-1,sizeof(h));

}


inline void add(int x,int y,ll w)

{

c[++esum]=w;

to[esum]=y;

nxt[esum]=h[x];

h[x]=esum;

}


inline bool bfs()

{

memset(dep,0,sizeof(dep));

queue<int> q;

q.push(s);

dep[s]=1;

while(!q.empty())

{

int u=q.front();

q.pop();

for(int i=h[u];i!=-1;i=nxt[i])

{

int v=to[i];

if(c[i]>0&&dep[v]==0)

{

dep[v]=dep[u]+1;

q.push(v);

}

}

}

return dep[t]!=0;

}


ll dfs(int u,ll w)

{

if(u==t)

{

return w;

}

for(int i=h[u];i!=-1;i=nxt[i])

{

int v=to[i];

if(c[i]>0&&dep[v]==dep[u]+1)

{

ll re=dfs(v,min(w,c[i]));

if(re>0)

{

c[i]-=re;

c[i^1]+=re;

return re;

}

}

}

return 0;

}


inline ll dinic()

{

ll ans=0;

while(bfs())

{

while(ll tmp=dfs(s,1e18))

{

ans+=tmp;

}

}

return ans;

}


int main()

{

init();

scanf("%d%d%d%d",&n,&m,&s,&t);

for(int i=1;i<=m;i++)

{

int x,y;

ll w;

scanf("%d%d%lld",&x,&y,&w);

add(x,y,w);

add(y,x,0);

}

printf("%lld\n",dinic());

return 0;

}

```



加了两个优化的:


```cpp

// P3376

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>


using namespace std;


typedef long long ll;


int n,m,s,t;

int esum,to[10005],nxt[10005],h[205];

ll c[10005];

int dep[205],cur[205];


inline void init()

{

esum=1;

memset(h,-1,sizeof(h));

}


inline void add(int x,int y,ll w)

{

c[++esum]=w;

to[esum]=y;

nxt[esum]=h[x];

h[x]=esum;

}


inline bool bfs()

{

memset(dep,0,sizeof(dep));

queue<int> q;

q.push(s);

dep[s]=1;

while(!q.empty())

{

int u=q.front();

q.pop();

for(int i=h[u];i!=-1;i=nxt[i])

{

int v=to[i];

if(c[i]>0&&dep[v]==0)

{

dep[v]=dep[u]+1;

q.push(v);

}

}

}

return dep[t]!=0;

}


ll dfs(int u,ll w)

{

if(u==t)

{

return w;

}

ll sum=0;

for(int i=cur[u];i!=-1;i=nxt[i],cur[u]=nxt[cur[u]])

{

int v=to[i];

if(c[i]>0&&dep[v]==dep[u]+1)

{

ll re=dfs(v,min(w,c[i]));

c[i]-=re;

c[i^1]+=re;

sum+=re;

w-=re;

if(w==0)

{

break;

}

}

}

return sum;

}


inline ll dinic()

{

ll ans=0;

while(bfs())

{

for(int i=1;i<=n;i++)

{

cur[i]=h[i];

}

ans+=dfs(s,1e18);

}

return ans;

}


int main()

{

init();

scanf("%d%d%d%d",&n,&m,&s,&t);

for(int i=1;i<=m;i++)

{

int x,y;

ll w;

scanf("%d%d%lld",&x,&y,&w);

add(x,y,w);

add(y,x,0);

}

printf("%lld\n",dinic());

return 0;

}

```



# Part 3 最小费用最大流问题


# Part 4 网络流求图的最小割


# Part 5 一些技巧




返回首页


Copyright (C) 2018-2022 huidong