网络最大流与最小截问题 -- EK算法详解


解决问题

对于一张图, 我们对于每条边有两个特性, 单位时间能传输的最大流量(容量)和流量, 流量必须小于等于容量并且对于每个点来说, 流入的流量和与流出的流量和必须相等. 最大流算法就是解决图中一个点到另一个点的单位时间内能传输的最大流量.


重要概念与定理

  • 流网络

    网络流都是针对有向图来说的,对于一个有向图,图中的每条边都存在两个特性,容量与流量,且对于每一个点都满足入出流量守恒,每条边的流量都小于容量,且存在一个源点和汇点,使得源点流出的流量之和等于汇点流入的流量之和,这样的有向图,我们称之为流网络。

  • 可行流

    可行流是针对整个图来说的, 对于整个无向图来说, 所有弧满足流量必须小于等于容量并且使得其端点合法(出入相等), 则我们称从起点流向终点的流量可行.

  • 残流网络

    对于原图的任一可行流,都存在一个残流网络与之一一对应。残流网络中,点集与流网络的点集相同,边集是流网络的两倍(原边集+反向边)。反向边的容量为对应可行流中的边的流量,正向边的容量为对应可行流边的容量-流量。

  • 弧(边(有方向的))
    1. 饱和弧(容量 = 流量)
    2. 非饱和弧(流量 < 容量)
    3. 零流弧(无流量)
    4. 非零流弧(流量 > 0)
  • 增广路径(基于当前的可行流或残流网络来说的)

    定义: 对于当前的残流网络来说,能够从起点走到终点的一条路径,并且路径中的弧都非饱和,我们称之为增广路径。那么我们在增加增广路径中弧的流量时,若弧为原流网络中不存在的弧,那么对应原流网络中的弧为阻碍流量流动的弧,我们增加当前弧的流量,相当于是减少原流网络中弧的流量,即减少阻碍流量流动的流量。增加原流网络中本来就存在弧的流量,相当于就是增大流量,从而增大整体的流量。也就相当于课上说的正加反减
    定理1: 对于一种可行流方案来说, 如果当前方案中还存在增广路径, 那么其总流量将还能得到增广, 使得其单位时间的流量更大.
    定理2: 动态相互影响, 当当前可行流方案中的一条增广路径被增广为非增广路径时, 那么图中调整前的其他增广路径, 现在就可能不是增广路径了.
    定理3: 当当前可行流方案中不再存在增广路径, 那么该图起点的流出流量就必定为最大流.

  • 截集与截量

    定义:

    1. 截集是指我们将图中的节点分为两个集合(V1, V2, V1 ∩ V2为空集, V1 ∪ V2为V), 并且S位于V1, E位于V2, 所有由V1指向V2的有向边的集合, 我们称之为该划分下的图的截集.
    2. 截量就是指截集中的所有边的容量之和.
      性质: 在图中删去截集之后, 起点到终点将不存在(注意这里指得是路,有向的).
      定理1(最大流最小截(割)定理): 网络的最大流量等于网络的最小截量. 由定理2可知,任一可行流的流量小于等于任一截集的截量,即当流量等于截量时,流量最大,截量最小。
      定理2: 网络中的任一可行流的流量小于等于任一截集的截量(容量,有限个). (那么该图的最大流量就等于最小的截量, 自然也就小于了其他截集的截量了)
      证明:
      定理2

算法分析

  • 标号法(EK算法)求解最小截集与最大流
    1. 算法思想: 通过找当前可行流中的增广链并对其增广, 直到可行流中无增广链为止, 那么当前可行流为最大流, 且以已标记点为V1, 未标记点为V2, 由V1连向V2的所有边的集合即最小截集.
    2. 算法实现: 对于一般的最大流问题, 我们开始的每条边的流量是没有给出的, 只给出了容量, 然而标记算法求最大流, 是通过增广链增广的, 所以我们开始的图的流量必须保证是一个可行流, 那么我们怎么构造一个尽量接近最大流的初始可行流呢? 对于每条边赋予尽量大的合法流量或者把所有的边流量全初始化为0, 即零流(虽然这样很远离最大可行流的流量, 因为当前可行流流量为0,但代码实现中我们这样做). 构造完之后, 对于每个走过的点我们记录下当前该点增广链的上一个点的编号,同时维护出当前增广链的最大调整流量。首先我们将起点标记, 我们对标记点集的所有弧(除开父边)进行延伸, 检查是否存在一条流出至未标记点的非饱和弧(增广路径中对弧的要求) – 即f[i]!=0&&!st[ver]. 有的话, 我们选择最快到达终点的路径走过去,将其加入队列, 然后标记该点, 继续寻找点集的弧, 当点集的所有弧都不符合的时候, 此时的可行流为最大流, 否则直到终点被标记. 此时被标记的一条链则为一条增广链. 我们对其进行增广, 那么如何增广呢? 我们对当前增广链的边增加d[T]的最大可调整流量(流量增大,当前容量将减少即f[i]-=d[T]),同时其反向边的容量对应增加,流量对应减少,得到一个新的残流网络,一个更大流量的可行流。

代码实现

O(n^2 * m)

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 20010, INF = 1e8; // INF为容量最大值

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; // 流量为0,零流
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ; // 容量为0相当于没有,也就是初始的可行流
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    q[0] = S, st[S] = true, d[S] = INF;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (!st[ver] && f[i]) // 点未被标记且若该弧为正向弧流量即非饱和
            {
                st[ver] = true;
                d[ver] = min(d[t], f[i]); // 得到增广链最大可调整流量
                pre[ver] = i; // 存储增广链
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int EK()
{
    int r = 0;
    // bfs一次,可行流变化一次
    while (bfs())
    {
        r += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T]; // 正向弧流过流量自然容量减少了,当f[i]==0,正向弧流量饱和
    }
    return r;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", EK());
    return 0;
}

现实应用

  1. 计算机交互
  2. 电路输送 -> 最大流
    虚拟源点在最大流问题中的应用 -> 类似其他图论问题, 节点含权值时想到虚拟源点
  3. 攻防问题 -> 最小截
    题目
    我们将点两两之间的多条路转化为一条路, 路的数量转化为路的权重, 截断路使得两个点不能连通, 即最小截集. 图的最大流就等于最小截集的截量, 权值和即路数量的和, 所以问题转化为了求图的最大流.
    陆地岛屿单向边: A, F换一下位置就行了, 根据题意只需求一边即可.
    而对于具体的截集边, 我们在遍历最大流方案下的所有已标记点集中的点, 分别遍历其出边, 如果e[i]未被标记则将i输出即可.
    图论问题中的建图及问题转换
  4. 旅行问题 -> 最小截
    题目
    车辆必过的边的集合其实就是截集, 这里的截量就是费用, 所以这道题就是求最小截, 即最大流.

问题拓展

如何通过扩容扩大最大流?
在最大流问题中, 我们最大流 = 最小截, 所以扩大最大流就是扩大最小截集的截量, 即截集中的边的容量.


参考资料

增广链
截集,截量与最大流最小截定理与EK算法详解
实际问题1
实际问题2


Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
EK算法求最小费用流 EK算法求最小费用流
写在前面,费用流也称作最小费用流. 给定流量的问题称为最小费用流问题, 给定流量为最大流的问题我们称为最小费用最大流问题. 解决问题求一个图中, 一个点到另一个点, 在保证最大流量的情况下, 求最小费用. 图中每条边有三个特性, 容量, 单
2020-07-04
Next 
图的割边求法汇总(基准, 并查集, Tarjan算法)及代码实现 图的割边求法汇总(基准, 并查集, Tarjan算法)及代码实现
If you want to read this article, please go to About page, scan wechat or alipay QR code, pay 200 yuan and contact blogger through QQ, then you can get the passsword and read the article.
2020-06-28
  TOC