【学员专栏011期】网络流之最大流问题-何佳龙 / 四六文摘

作者：何佳龙
ID:hjl666
学校：长沙市中雅培粹七年级
获奖：2019年普及组一等奖，提高组二等奖
博客地址：
https://www.luogu.com.cn/blog/hjl666/wang-luo-liu-zui-da-li

最大流

摘要

在最大流问题中，我们意在寻找一个带权有向图G中从一个特定的源点s到一个特定的汇点t的最大流。

寻找最大流有几种不同的算法，包括Ford Fulkerson算法，Edmonds Karp算法和Dinic算法

最大流的对偶问题是最小割，也就是在寻找图G的最大s-t流的同时找到图G的最小s-t割，也就是为了使图G中s和t不连通所需要移除的权重最小的边的集合。

例题引入：

你所在的村庄新开通了地下流水管道，自来水厂源源不断的提供水，村民们用水直接或间接用水，而村庄用完的废水统一回收于另一点(设排来的水全部回收)。当然每个管道有一定的容量，废水站求出最多可以汇聚多少水？

想一想：

提取关键信息：

首先水是源源不断的，经过了有限制流量的管道，求最多能流入多少水

所以：

1.实流量<=限制流量

2.对于每个除源汇之外的点：总流入量=总流出量

思考做法

首先我们想可以先dfs一遍，找一条路

再在剩下的网络中找其他的路径并将其加入答案

但这时会发现，开始选的答案可能会影响后续更优的答案，即局部最优解不是全局最优解，那么我们想到可以让其有回退--即反悔的机会，使最后的解一定是最优解

引入概念：

（大致理解即可）

流量：每条边各自被经过的次数称作其流量，最终收集的总数为整个流的流量

容量：每条边都有一个容量

w（x,y）容量限制

flow（x,y）从x到y的是实流量

增广路径：从s到t找到一条流量非0的路径

残余网络：将非增广路径边正方向建图，增广路径上的边反方向建图

反悔机制

当你用dfs找到一条增广路径时，可能不是正确答案（想想就知道

那么我们可以将增广路上的边建反边--即反悔机制

总结做法

1.在图上找到一条从源点到汇点的路径--增广路

2.在残余网络中接着找，累加至ans

3.同时继续建反边

4.直至无法到达。

这便是：Ford-Fulkerson算法

出大问题：时间！！！

于是就有了Edmond-Karp算法

EK算法 O

1.bfs找增广路径

2.更新残余网络

3.重复1,2步，直至找不到

代码

bool bfs() { memset(vis, 0, sizeof(vis)); queue<int> q; q.push(s); vis[s] = true; increase[s] = inf; //最小剩余容量 while(q.empty() == false) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = nxt[i]) if(edge[i]) //容量不为0 { int y = to[i]; if(vis[y] == true) continue; increase[y] = min(increase[x], edge[i]); pre[y] = i; q.push(y); vis[y] = true; if(y == t) return true; } } return false;}

比较

FF用dfs找路径

EK用bfs找最短路径

Dinic算法 O

EK算法后，时间复杂度似乎还不够优化，那我们能不能使时间更优呢，在EK中，我们已经是有每次去一个最优解，所以在找法上似乎已经没办法了，这时注意到我们每次只找一个，那为什么不一次找多条么？？

思想：一次找几条

实现

bfs找各个点距s的层次

dfs找多条路径

演示

首先标记每个点的层次

找到一条路径

接着在残余网络中标记每个点的层次

再次在残余网络中寻找路径

最终无路可选

代码

int dinic(int x, int flow) //x当前结点， flow表示当前的容量限制 {    if(x == t)         return flow; //返回增广流量    int rest = flow, increase; //剩余的流量    for(int i = head[x]; i && rest; i = nxt[i])    {        if(edge[i] && level[to[i]] == level[x] + 1) //流量非0，层次加1的点我才去        {            increase = dinic(to[i], min(rest, edge[i]));//找从to[i]出发到达t能得到的增广流量            if(increase == 0)                 level[to[i]] = 0; // 去掉增广完毕的点, 剪枝             edge[i] -= increase; //正向边i扣除流量            edge[i ^ 1] += increase; //反向边增加流量            rest -= increase;        }    }    return flow - rest; //增广的流量 = 容量上限 - 剩余的流量 }

例题讲解

P2766 最长不下降子序列问题

第一问dp即可

第二问：对于满足条件的，连一条容量为一的边

第三问：对于满足条件的，除x1和xn外连一条容量为一的边，否则连一条容量为无穷大的边

代码

自己看题解吧~

备注

若有哪里不懂得欢迎提出意见~

【学员专栏011期】网络流之最大流问题-何佳龙

最大流