[图论]网络流学习笔记-Isap算法原理

· · 算法·理论

Part 1 网络流介绍

进阶知识：[图论]网络流练习笔记-Isap算法应用

网络流是算法竞赛中的一个重要的模型，

是图论中的一种理论与方法，研究网络上的一类最优化问题 。

网络流中最常见的问题就是网络最大流。

问题简述

洛谷-P3376 【模板】网络最大流

给定指定的一个有向图,其中有两个特殊的点：源点S(Sources)和汇点T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

通俗的讲，现有一组自来水管道系统，由若干节点和连接节点的若干条管道构成。在单位时间内，每条管道都有一个可通过流量的最大值，称为容量。在源点可以无限制提供水量的前提下，水流将在由节点连接的不同管道流进流出。而在现有条件下，在汇点处最多可以汇集多少水流？

名词概念

网络流分为两部分：网络和流。

网络(network)

网络，其实就是一张带权有向图，其上的边权称为容量。额外地，它拥有一个源点(简称S)和汇点(简称T)。

在求解过程中，网络可以细分为3个部分：容量网络、流量网络、残留网络。

容量网络就是关于容量的网络，基本是不改变的(极少数问题需要变动)；

流量网络就是关于已通过流量的网络 在求解问题的过程中通常在不断的改变，调整到最后就是最大流网络，同时也可以求得最大流值；

残留网络(Residual networks) 就是关于待通过流量的网络，往往概括了容量网络和流量网络，是最为常用的。

残留网络=容量网络-流量网络；

流(flow)

流，顾名思义，就像水流或电流，也具有它们的性质。如果把网络想象成一个自来水管道网络，那流就是其中流动的水。每条边上的流不能超过它的容量，并且对于除了源点和汇点外的所有点(即中继点)，流入的流量都等于流出的流量(即流守恒性)。

割集(cut set)

分割点集合和割边集合(下文割集均指割边集合)。

将图G分为A和B两个点集，A和B之间的边的全集则称为图G的割集。

换句话说，删去若干条边，使得图G恰分为互不连通的两个子集，则这些边组成割集。

特殊地，若存在只含一条边的割集，则称这条边为桥。

增广路(augment path)

增广，即为经过某条固定路径向汇点提供流量，扩大当前的总流量。

增广路是一条从源点(S)到汇点(T)的路径，路径上每条边残留容量都为正值。

增广路能够增广的流量，是路径上最小残留容量边决定的，其值即为此边残留容量。

现实意义及历史背景

网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和 D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D=(V、E、C) ，其中 V 是该图的顶点集，E 是有向边(即弧)集，C 是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点 v1 - v6 表示 6 座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点 v1 将物资运送到终点 v6 去 ，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1 表示发送点，v6 表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从 v1 到 v6 的总运输量为最大。这样的问题称为最大流问题。——百度百科

Part 2 网络流性质

对于任意一个时刻，网络流都有三条基本性质。

设c(u,v)为点u到点v的容量，f(u,v)为点u到点v的实际流量，

容量限制(Capacity Constraints)

f(u,v)≤c(u,v)

一条边的流量不能超过它的容量。

斜对称性(Skew Symmetry)

f(u,v)=-f(v,u)

由u到v的净流量必须是由v到u的净流量的相反值。

流守恒性(Flow Conservation)

∀u∈V且u≠S or T，∑f(u,v)∈E=0

即u相连的边权和为0，因为流入u的流量和流出u点的流量相等，u点本身不会"制造"和"消耗"流量，除了"制造"流的源点和"消耗"流的汇点。

增广路定理(Augmenting Path Theorem)

网络达到最大流当且仅当残留网络中没有增广路

最大流最小割定理(Maximum Flow Minimum Cut Theorem)

Max-flow=Min-cut(最大流等于最小割)

在网络中，汇点(T)所得到流量的不确定性在于中继点可自由分配流入流量以不同方案流出。然而不是所有流入流量都能流出，不是所有流出流量最终都能流入汇点(T)，分配方案的差异会导致结果(汇点流量)的不同。在所有可行结果中，拥有最大值的分配方案及结果被称为网络最大流。

在网络中，可令源点(S)和汇点(T)不连通的边权和最小的割边集合被称为网络最小割。

最大流的流量恒等于最小割的权值，可推得网络的任意割恒大等于任意流。

Part 3 网络最大流求解算法

FF算法

全称Ford-Fulkerson算法，即增广路算法。

大体步骤：

  1. 建图同时存正反边，正边权为容量(可视为初始残留流量)，反边权为零，而在后续过程中所有边权均代表残留流量；

  2. 搜索实现：通过dfs遍历图寻找一条可行增广路；

  3. 边界实现：将该路的增广流量计入总流量；

  4. 回溯实现：将该路每条边正向减去增广流量，反向加上增广流量；

  5. 循环实现：重复上述过程直至无可行增广路为止；

  6. 最大流即为当前总流量。

详解：

该算法思路难点主要体现在步骤三。

在建图过程时，对每条原边同时存入其对称边(新边)，两边关系是互为反向边且流量对称(流量和=容量)，作为流量斜对称性的具体表现。

在跑图过程中，无差别的对所有边(包括原边和新边)进行搜索，并在回溯时修改并维护流量斜对称性原则，此过程即为步骤三的意义体现。

那么为什么这个操作是正确、可行且必需的呢？

如果不存对称边的话，大家可以找组数据按步骤模拟一下，很显然结果是错的。

假设存在增广路径上的一条边A --> B，我们可以将网络简化为上图，其余任意两点的直线代表两点间不经过图上其他点的所有路径，增广路径为S --> A --> B --> T。

抽象地说，在修改时，我们会压缩S --> A和B --> T的流量潜力。但对于S --> A --> T和S --> B --> T来说，这意味着A --> T流量潜力的空余和S --> B流量潜力的多余，因为其前后两边压缩了而这两边无变化，后果就是流量资源的浪费和最终总流量的减少，所以说又额外压缩的部分全网络的流量潜力，额外压缩潜力即为增广流量(即A->B减去的值)。

因此，我们需要相应增加B -->A 的值，使得S --> B流量潜力的多余能被引导入A --> T流量潜力的空余，恰好弥补回额外压缩的潜力损失，而弥补(B --> A)所增加的值即为额外压缩(A --> B)所减去的值。

由此，可确定该操作的正确性、可行性和必需性。

注：以上解释均为笔者个人的理解，不必深究。

其它

Q：FF算法如何保证最终无增广路？

A：可以理解为全网络的流量潜力不断压缩，最终会变为零。

Q：如何得知最终总流量即为最大流？

A：每次增广的流量会扩大汇点当前的总流量，无增广路意味着没法再使总流量更大，可得此时总流量将成为最大流。(增广路定理)

总时间复杂度上界为O(E·max-flow)，平均时间复杂度为O(玄学)。

随机图时间勉强过关，尚有较多优化空间。

EK/SAP算法

全称Edmonds−Karp/Shortest Augumenting Path算法，即最短增广路算法。

该算法与FF算法的区别在于，FF算法中随机寻找增广路，而EK算法中总是寻找最短的增广路，即源汇间增广路的点数(边数)最少。

算法通过BFS广搜实现寻找增广路。从源点开始不断新加点入队，若首次到达汇点即能获取最短增广路，由此进行下一步操作。重复上述过程即可。

算法的BFS增广次数复杂度上界为O(V·E)，通常效率远优于FF算法。

总时间复杂度上界为O(V·E^2)。

ISAP算法

全称Improved Shortest Augumenting Path算法，即最短增广路优化算法。

ISAP算法是当下平均效率最高的网络最大流算法，仅次于HLLP预留推进算法。

阅读此算法之前，请先确保阅读过前置两篇算法。

同样是最短增广路算法，ISAP通过DFS实现增广，并为此引入新的数组辅助。与EK算法相比，ISAP的一次DFS可进行多次增广，而EK算法一次BFS只有一次增广。

首先预处理通过BFS实现，类似EK算法，但是这里需要从汇点开始加点入队，同时将每个点到汇点的最短距离存入新的数组，称为高度数组。

然后在寻找增广路的过程中，DFS只允许节点间在高度相差1的条件下有高到低走，可以保证所得的增广路是最短的。

当增广时某个点可走的流量已经全部消耗后，即没有比它低一层的节点相连时， 就将该节点的高度上升一层再同时回溯，进行其他路径的增广。单次DFS至少能增广耗尽1个节点现有高度下的全部流量(即升高1个节点)。

寻找增广路的结束条件是源点的高度大于总点数，这意味中其中必有高度出现断层，源汇之间无法继续找到高度递减的增广路，最大总流量已统计完成。

当然算法需要进行多次的DFS，然而因为单次DFS增广的次数和流量更多，效率高于EK算法，其DFS的次数也要更少，复杂度上界为O(V^2)，更优于EK算法。

可以结合下文代码加深理解。

总时间复杂度上界为O(V^2·E)。

Part 4 网络流Isap算法优化

当前弧优化

当前弧优化是个普遍有效的常数效率优化方法，适用于复杂建图和朴素网络流。

该优化主要通过在循环上重设起始标号来达到减少重复冗余判断的目的。

void Init_net(){
    ……
    for(i=1;i<=tot;++i)cur[i]=beg[i];
}
int Isap(int u,int flw){
    ……
    for(i=cur[u];v=go[i];cur[u]=i=nex[i]){
        ……
        return *;
    }cur[u]=beg[u];
    return *;
}

Gap优化

Gap优化同样是个极其有效的常数效率优化方法，适用于网格建图和分层建图。

该优化主要通过断层判断来达到提前结束程序的目的。

void Init_net(){
    ……
    for(i=1;i<=tot;++i)++gap[lab[i]],;
}
int Isap(int u,int flw){
    ……
    for(i=beg[u];v=go[i];i=nex[i])
        ……
        return *;
    if(!--gap[lab[u]])lab[st]=tot+1;
    ++gap[++lab[u]]；
    return *;
}

Part 5 网络流Isap算法代码

洛谷提交记录

注意：

  1. 如果使用链式前向星建图，从2号开始存边（cnt初始值设为1）；

  2. 终点层次编号设为1而不要设为0，否则终点将被重编号；

#include<iostream>
#include<cstdio>
#include<queue>
#define P(i,j) (~-(i)*m+(j))
using namespace std;
const int INF=0x7fffffff;
const int N=201;
const int M=10001;
int cnt=1,beg[N],nex[M],go[M],len[M];//链式前向星存图
int tot,lab[N],cur[N],gap[N];//网络相关：高度数组，弧数组，层数组
int n,m,st,en;
long long ans;
inline void fip(int& rer){
    register char ch;
    for(ch=0;ch<'0'||ch>'9';ch=getchar());
    for(rer=0;ch>='0'&&ch<='9';ch=getchar())
        rer=(rer<<3)+(rer<<1)+(ch^48);
}
inline void adde(int u,int v,int w){
    nex[++cnt]=beg[u],beg[u]=cnt;
    go[cnt]=v,len[cnt]=w;
    nex[++cnt]=beg[v],beg[v]=cnt;
    go[cnt]=u,len[cnt]=0;
}
void Init_graph(){
    register int i;
    for(i=1;i<=tot;++i)
        lab[i]=gap[i]=0,
        cur[i]=beg[i]=0;
    for(i=1;i<=cnt;++i)
        nex[i]=go[i]=len[i]=0;
    cnt=1,tot=st=en=0;
}
void Init_net(){
    register int i,u,v;queue<int>Q;
    for(lab[en]=1,Q.push(en);!Q.empty();Q.pop())
        for(i=beg[u=Q.front()];v=go[i];i=nex[i])
            if(!lab[v])lab[v]=lab[u]+1,Q.push(v);
    for(i=1;i<=tot;++i)++gap[lab[i]],cur[i]=beg[i];
}
int Isap(int u,int flw){
    if(u==en)return flw;
    register int i,k,v,tmp=flw;
    for(i=cur[u];v=go[i];cur[u]=i=nex[i]){
        if(lab[u]!=lab[v]+1||!len[i])continue;
        flw-=k=Isap(v,min(flw,len[i]));
        len[i]-=k,len[i^1]+=k;
        if(!flw)return tmp; 
    }if(!--gap[lab[u]])lab[st]=tot+1;
    ++gap[++lab[u]],cur[u]=beg[u];
    return tmp-flw;
}
int main(){
    register int i,u,v,w;
    scanf("%d%d%d%d",&n,&m,&st,&en);
    for(tot=n,i=1;i<=m;++i)
        fip(u),fip(v),
        fip(w),adde(u,v,w);
    Init_net();
    while(lab[st]<=tot)
        ans+=Isap(st,INF);
    printf("%lld",ans);
    return 0;
}

Part 6 后记

Thx for reading

Uploaded on 2021-12-12

For schoolwork