网络流是模仿水流解决生活中类似问题的一种方法策略, 来看这么一个问题, 有一个自来水厂 S, 它要向目标 T 提供水量, 从 S 出发有不确定数量和方向的水管, 它可能直接到达 T 或者经过更多的节点的中转, 目前确定的是每条水管中水流的流向是确定的(单向), 且每个水管单位时间内都有属于自己的水流量的上限(超过会爆水管), 问题是求终点 T 单位时间内获得的最大水流量是多少? 如下图:
1. 首先, 我们用正常的思路去解决这个问题, 对于上图的情况而言, 我们可以先选择一条水流的路线 1->2->4, 而且我们得知 1->2 水管水流量上限为 40, 而 2->4 水管水流量上限只有 20, 则这一条路径通往终点 T 的水流最大值为 20, 而这么走的话, 1->2 的水管中剩余水流量则为 40-20=20,2->4 水管中的剩余水量为 20-20=0, 注意: 这里水管剩余流量为 0 后说明这条路径就再也不能接通了, 或者说它已经被完全占用了, 此时终点 T 单位时间获得水量 0+20=20
2. 然后我们继续选择一条不包含 0 流量的从 S 到 T 的路径, 比如 1->2->3->4, 此时 1->2 上水流量剩余 20,2->3 剩余 30,3->4 剩余 10, 很显然这条路径上最终能为终点 T 提供的单位时间的水量由路径上的最小剩余流量 10 决定(就像是木桶的短板效应一样), 这么走的话, 1->2 水管中剩余的水量为 40-20-10=10,2-3 水管中剩余的水量为 30-10=20,3->4 水管中剩余的水量为 10-10=0, 它也被完全占用了, 此时终点 T 单位时间获得水量为 20+10=30
3. 我们继续找还能找到一条从 S 流向 T 的路径 1->4, 水流上限 20, 因为是直达的, 所以路径上最小剩余流量就是它本身, 则这么走的话, 1->4 上的水流量全部耗尽, 20-20=0, 它也完全被占用了, 而终点 T 再一次获得 20 水量, 30+20=50, 至此整张网络流图再也找不到一条能从 S 到 T 的不包含 0 流量的通路, 终点 T 单位时间获得的最大水流也计算出来得到 50
但是, 上述的推理只是碰巧数字比较合适让我们轻而易举得到了 50 这个看似正确的结果, 实际上存在着缺陷, 假如我第一次找的一条路径并不是此时的最优解, 并且这么选使得我下一次选择别的路径的时候有的水管流量已经被占完了, 我想反悔怎么办
如下图: 如果我们第一次选择的是 1->2->3->4 这条路径(这很符合程序设计的观念, 计算机很容易就按照序号去查找), 那么 1->2 水管剩余流量为 1-1=0,2->3 水管剩余流量为 1-1=0,3->4 水管的剩余流量为 1-1=0, 至此我们发现所有的通路都被这三个 0 流量的水管阻断了, 而此时终点 T 获得的单位水量只有 0+1=1
按正常的人为的思路, 此时我想要反悔之前选的那条路径, 同时选择别的路径, 而下图的 1->2->4 和 1->3->4 这两条路径的选择才是这张网络流图的最优选择, 终点 T 得到的最大水量为 1+1=2, 而 2->3 的这条水管我们放弃不用
上述反悔的过程在我们的思维看来确实可以 (假装) 没有走过 2->3 这条路, 但是计算机并不能这么去主动理解这种情况, 它应该按并不是最优的情况去尝试, 当遇到可能更优的情况时更改之前的选择, 在我们设计程序的时候, 如何能做到这个反悔的过程呢, 关键来了: 我们对于每次选择的一条道路上的每个水管都要减去路径上的最小残量的同时, 为这两个相邻的点添加一条反向弧, 反向弧的数值加上最小残量的数值, 如上上图那个并不是最优的走法, 假设计算机确实第一次就选择了这条路径, 那么我们做出如下处理: 1->2 剩余流量依旧为 1-1=0, 而同时添加一条 2->1 的反向弧, 流量为 0+1=1(反向弧也是一条通路, 它的存在就像是为我们提供了一个返回的机会),2->3 剩余流量为 1-1=0, 添加 3->2 的反向弧, 剩余流量为 0+1=1, 同样 3->4 的剩余流量为 1-1=0, 而 4->3 的反向弧上的剩余流量为 0+1=1, 所以本次选择之后终点 T 依旧获得了 1 的单位流量
接下来我们继续选择一条路径, 1->3->2->4(当然也只剩下这条了), 此时我们如上述操作, 为 1->3 剩余流量, 3->2 剩余流量, 2->4 剩余流量都减去这条路径上的最小残量 1, 同时为它们两两之间的反向弧增加上这个最小残量 1(图可能有点乱, 但是原理是不变的, 实线方向 -, 虚线方向 +), 至此, 1->2=0,2->1=1,1->3=0,3->1=1,2->3=1,3->2=0,2->4=0,4->2=1,3->4=0,4->3=1, 从 S 到 T 已经没有一条额外的路径不包含 0 流量了, 此时 T 获得最大单位水量 2, 并且通过这种建立反向弧的方式, 我们对于从 2 到 3 再从 3 到 2 都走了一遍, 这不就好像是模拟了一遍反悔的过程吗(具体证明这里不作详述), 接下来讲解 EK 算法
铺垫了这么多终于要讲解 EK 算法了
别着急在讲解 EK 之前我们需要介绍几个网络流中最重要的概念, 我们称起点 S, 也就是水流的出发点为源点, 将水流的终点 T 称为汇点, 而我们每一次找一条从源点到汇点的不包含 0 流量的路径称为增广路,(增广路顾名思义, 如果能找到一条从 S 到 T 的增广路, 则到终点的水流量一定还可以增加至少 1, 所以就满足了增广这个要求了), 其实求网络流最大流的问题的各个算法都是在模拟一个找寻增广路的过程, 如果找不到了就说明此时终点获得的水量将无法变得更大, 答案就算出来了
EK 算法: 从 S 点出发不断找一条到 T 的增广路的过程, 我们通过 BFS 向周围搜索与 S 直接相连的剩余流量不为 0 的节点(这个节点一定要是没走过的, 因为一条增广路每个点肯定值出现了一次), 将他们加入队列, 每次从队列中取出一个元素继续向周围查询, 直到目标点为 T 点, 且这一条道路上不包含流量为 0 的水管, 则说明这是一条增广路, 为沿途的所有节点两两之间的剩余流量减去该条增广路的最小残量, 而同时为它们的反向弧加上最小残量, 不断循环直到无法从 S 点到 T 找到一条增广路为止
这里推荐一题网络流最大流的模板题, POJ1273, 题面讲的是有 n 个水管, 有 m 个点, 源点为 1, 汇点为 m, 求汇点 T 单位时间的最大水流量, 当然这题有个小坑, 就是输入会重复, 如果 1->2 40 代表从 1 流向 2 有 40 流量, 那可能会有多次 1->2 40,1->2 30 之类的, 要累加成 1->2 70
代码:
- #include<iostream>
- #include<stdio.h>
- #include<queue>
- #include<string.h>
- using namespace std;
- const int N = 205;
- const int INF = 0x3f3f3f3f;
- int c[N][N]; // 记录 i 到 j 的剩余流量
- int p[N]; //p[i]记录流向 i 点的前驱节点
- int v[N]; // 记录在一条增广路中, 流到 i 点时, 此刻增广路上残余量的最小值, 直到 i == m 时就是整条增广路上的残余量最小值
- int n, m;
- int min(int a, int b){
- return a <= b ? a : b;
- }
- void EK(){
- // 从 1 出发, 不断找可以到达 m 的增广路
- int ans = 0;
- while(true){
- //EK 算法的核心是通过 bfs 不断查找增广路, 同时建立反向弧
- // 每次循环都要对 v 数组和 p 数组进行清空, 因为是意图查找一条新的增广路了
- memset(p, 0, sizeof(p));
- memset(v, 0, sizeof(v));
- queue<int> q;
- q.push(1);
- v[1] = INF;
- // 每次只找一条增广路, 同时修改 c[i][j]的值
- while(!q.empty()){
- int f = q.front();
- q.pop();
- for(int i = 1; i <= m; i++){
- if(v[i] == 0 && c[f][i]> 0){ //v[i]原本是记录增广路实时的残量最小值, v[i]==0 代表这个点还没有走过, 且从 p 到 i 的残量大于 0 说明通路
- v[i] = min(v[f], c[f][i]); // 实时更新 v[i]的值, v[f]存储 1 条增广路中 i 点前所有水管残量的最小值, v[i]为该条增广路到 i 点为止, 路径上的最小残量
- p[i] = f; //p[i]实时保存 i 点的前驱节点, 这样就当 i==m 时整条增广路就被记录下来
- q.push(i); // 将 i 点入队
- }
- }
- }
- if(v[m] == 0) break; // 如果 v[m]==0 则代表找不到增广路了(中途出现了 c[i][j]==0 的情况)
- ans += v[m];
- int temp = m;
- while(p[temp] != 0){ // 类似并查集的查操作, 不断查上一个元素且将剩余残量减去最小残联, 反向弧增加最小残量
- c[p[temp]][temp] -= v[m];
- c[temp][p[temp]] += v[m];
- temp = p[temp];
- }
- }
- printf("%d\n", ans);
- }
- int main(){
- while(scanf("%d%d", &n, &m) != EOF){
- memset(c, 0, sizeof(c));
- for(int i = 1; i <= n; i++){
- int x, y, z;
- scanf("%d%d%d", &x, &y, &z);
- c[x][y] += z; // 初始时, 从 x 流向 y 的剩余流量就是输入的值
- }
- EK();
- }
- return 0;
- }
来源: https://www.cnblogs.com/findview/p/11314610.html