网络流 - 最大流

阅读量：4578 次

发布时间：2019-06-08

本文共 7393 字，大约阅读时间需要 24 分钟。

欢迎访问~原文出处——

网络流 - 最大流

问题模型

有一个图，G∈(V,E,C)，其中V表示节点集合，E表示边集，C表示边的容量集。

我们用3个量描述一条边：起始点(x)，结束点(y)，容量(cap)。

在这个图中，有两个特殊的点，一个是源点(s)，一个是汇点(t)。

最大流是网络流的问题中的一个重要部分。

最大流就是求从源点出发，到达汇点，每条边的流量<=该边容量，使得流入汇点的流最大为多少。

比如下图的最大流为7。

路径为：(三条，橙色流量为2，绿色为2，蓝色为3)

解决此类问题的主要算法为增广路算法，当然还有预流推进等算法。

这里主要来介绍增广路算法。

增广路

首先，我们要了解一个“残量网络”的概念。

残量网络：在原网络中已经确定几条流之后，原图的点集、边集以及剩余容量集合所构成的网络，如上图去除绿色路径之后的残量网络为：

增广路：在当前剩余网络中的一条增广源点和汇点的流量的合法路径。其中，增广路可以走反向边。如上图的一条增广路为：

在通过增广路径求出残量网络的时候，我们在该边的正向边流量(flow)上加上该路径流量（当然要保证flow<=cap），在其反向边流量中减去该路径的流量。

那么，该图的残量网络为：

当然，增广路也可以经过反向边：

此图的残量网络为：

增广路算法的主要思路就是不断寻找增广路，最终使得残量网络不再有增广路，这样就结束了。

现在为止，反向边这个概念仍然是一个谜。

反向边是多数增广路算法中的重要部分。增广路可以从反向边走，大大提升了增广路算法的性能。

我们设有一条i->j的边，容量为C(i,j)，那么我们要对应的建立一条反向边，其容量为0,那么其流量一定会小于0。（想想为什么要这样）

这样就完美的限制了流量，保证了每条边的流量不会超过C(i,j)，且不会出现逆向流。

重申一遍：我们在给边 i->j 增加 k 的流量的同时，也会给边 j->i 减去 k 的流量，因为他们是互逆的。

SAP算法

用增广路一类方法解决这类问题的算法有很多，比如说EK算法、Dinic算法、SAP算法等。

这里介绍SAP算法，其他的读者可以去自学。

SAP算法基于增广路（这句话貌似说过了），采用不断增广的办法求取最大流。

大概是这样的：

首先一遍反向bfs，对于整个图，生成一个dist数组，dist[x]表示x节点到达汇点至少要经过几条边。这个操作不做也行，但是据说做了可以快常数倍。

然后SAP的关键部分。

SAP和Dinic有一定的相似度，也要给整个图进行分层，然后根据层找增广路。

初始化的时候，用num[]计数器累计所有层的节点个数。

SAP有两个比较简单的优化，一个是当前弧优化，一个是GAP优化（也就是断层优化）。Num[]计数器是为了为GAP优化做准备，而下面介绍的初始化部分，就是为当前弧优化做准备。

然后，我们用cur[i]表示第i个节点当前增广到的弧(边)的编号，初始化为节点i的第一个子节点（fst[i]）。

然后当前节点x从源点s开始关键部分。

关键部分貌似是一个dfs，但是写成了while。

为了寻找增广路，我们去寻找x所连向的节点是否满足构成增广路径的条件。有2个条件，一个是层数比x少1，即dist[x] == dist[y] + 1 ；一个是有剩余容量。

如果满足以上的两点，那么走向节点y之后就可能会形成一条新的增广路径，于是，我们会先记录路径（在最后的返回统计的时候，我们需要知道一个节点的前驱路径，所以我们会把当前路径的编号记录在节点y上）到p[y]上，记录当前弧编号（后面返回的时候可以避免重复，优化时间），并转向y，继续增广。

当然还有可能有当前的节点的后继节点已经枚举完毕的情况，这个我们放到后面去说。

当我们不断往（可能的）增广路径深处探寻的时候，最终会探寻到汇点t，那么我们就成功的发现了一条增广路。接下来我们的任务就是还原整个路径，改变目前最大总流量，改变路径上的边的最大总流量。之前记录了路径，记录了路径上每一个节点的前驱边，那么我们就可以沿着前驱走。那么增广路流量（ex_Flow）为多少？增广路上的每一条边的流量都不可以大于其容量，所以，我们选择剩余容量最小值，就是该增广路流量。然后对于每条边的当前流量，加上该增广路流量，对于每条边的逆向边当前流量，减去增广路流量。当然总的最大流要加上这个增广路流量。

然后我们总得回去吧，所以我们要寻找断点。这个点就是那个减去增广路流量之后剩余容量为0的边的前驱节点。

举一个例子：

UPD(2018-03-29):这两幅图没有汇点，是当时博主的一个疏忽，请读者脑补：最右侧三个点中，上面两个点都连向最下面的点。

比如当前剩余网络的增广路为红色路径。

那么增广路流量为3，下图三角形标记节点连出的边在此次增广之后容量为0。

那么我们暂时无论如何都不可以从这条路径的三角形节点连向三角形节点之后的节点这一类路径进行增广了，因为这条路径已经没有剩余容量了。那么我们就要回到三角形节点，继续增广。

所以我们要寻找的断点就是此次增广之后的剩余容量为0的边的前驱节点。有多个剩余容量为0的前驱节点怎么办？随便选择一个都没事。

再仔细思考，其实寻找这个断点，按照意义，我们要寻找最前面的那个。但是，如果我们选择了这个断点之后的任意点，得到一个增广路之后，增广路流量一定是0（为什么，自己想），不影响正确性。但是会慢一点。

现在回过来讲后继节点枚举完毕的情况。

此时，从该节点x已经无法继续增广了。那么其实有些连出去的边容量为0，没了！

那么节点x距离汇点t的最小边数变了，需要从它的子节点来更新，以进行后来的增广。

更新之后，x的层次变了，我们把x原来所在的那一层的节点个数-1，新到的+1。如果x原来那一层在减过之后就没有节点了，那么可以直接返回当前的最大流。这就是GAP优化。因为这一层没有节点了之后，出现断层，就无法找到合法的增广路了（结合上下文仔细分析）。

如果没有出现断层，那么我们回到x的前驱节点继续增广。

说到这里，SAP的具体实现已经说的差不多了。具体可以再结合代码进行理解和学习。

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=200+5,M=N*2;int n,m;struct edge{    int x,y,cap,flow,nxt;    // x,y 边的两个节点, cap 容量, flow 流量, nxt 指向 x 的下一条边 };struct gragh{    int cnt,fst[N],dist[N],s,t,num[N],cur[N],p[N];    int q[N],head,tail;    edge e[M];    void set(int S,int T){
   //初始化         s=S,t=T,cnt=1;        memset(fst,0,sizeof fst);        memset(e,0,sizeof e);    }    void add(int a,int b,int c){        // 建立正向边，容量为c         cnt++;        e[cnt].x=a,e[cnt].y=b,e[cnt].cap=c,e[cnt].flow=0;        e[cnt].nxt=fst[a],fst[a]=cnt;        // 建立反向边，容量为0         cnt++;        e[cnt].x=b,e[cnt].y=a,e[cnt].cap=0,e[cnt].flow=0;        e[cnt].nxt=fst[b],fst[b]=cnt;    }    void re_bfs(){        memset(dist,-1,sizeof dist);        memset(q,0,sizeof q);        head=tail=dist[t]=0;        q[++tail]=t;        while (head
          
           e[i].flow){ p[y]=cur[x]=i,x=y,found=1; break; }//找到一条可能为增广路的路径 } if (!found){ int d=n+1; for (int i=fst[x];i;i=e[i].nxt) if (e[i].cap>e[i].flow) y=e[i].y,d=min(d,dist[y]+1); if (!(--num[dist[x]])) return MaxFlow;//传说中的GAP优化 num[dist[x]=d]++; cur[x]=fst[x]; if (x!=s) x=e[p[x]].x; } } return MaxFlow; }}g;int main(){ while (~scanf("%d%d",&m,&n)){ g.set(1,n); for (int i=1,a,b,c;i<=m;i++) scanf("%d%d%d",&a,&b,&c),g.add(a,b,c); g.re_bfs(); printf("%d\n",g.ISAP()); } return 0;}

二分图匹配

二分图是指一类图，在这类图中，可以把所有的点分成两个集合，使得每一个集合的任意两点没有连边。

在解题过程中，我们常常会碰到一些题目，需要用到二分图匹配。

首先给一个例题：

一个二分图可以分为两个点集，分别为点集A和点集B，A中的节点互相没有连边，B中的节点也是这样。

对于点集A和点集B之间的连边，只从A到B。

现在给出A和B的点个数a，b，以及边数m，让你求二分图最大匹配。

举一个例子：

那么最大匹配为3

方案为：

1->6

2->7

3->5

当然也有其他方案。

那么如何用网络流Solve这类问题呢？

在左侧点左边建立一个超级源点s，从s向左侧的每一个点连接一条路径，容量为1；每条原图中的路径，照样连，容量为1；再建立一个超级汇点t，每一个右侧的点连一条边向t，容量为1。然后跑一跑最大流就是最大匹配数了。

至于还原路径，只要寻找满流的边即可。

但是，实际上，解决这类问题还有一个匈牙利算法。

匈牙利算法的原理其实也是寻找增广路。只不过容量和流量非0即1。那么我们就可以用一些特殊的方法来寻找增广路。

比如我们要给节点四匹配节点。

红色为当前的匹配点，蓝色的为某节点其他的边。

那么，如果找增广路的话，我们不难找到一条增广路为：

4->8->3->7->2->5，容量为1。

那么匈牙利也差不多。

4要匹配8，那么我们可以看3是否可以在不匹配8的情况下完成匹配，并不影响之前的最大匹配。

那么3只有匹配7；那么我们就要看2；2可以匹配5，5还未被匹配，所以2就成功匹配了5。

没什么好说的，接下来放代码，结合上面的例子理解上面的代码。

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=100+5;int m,n,a,b,match[N];bool g[N][N],vis[N];bool dfs(int k){    for (int i=1;i<=n;i++)        if (g[k][i]&&!vis[i]){            vis[i]=1;            if (match[i]==-1||dfs(match[i])){                match[i]=k;                return 1;            }        }    return 0;}int main(){    memset(g,0,sizeof g);    scanf("%d%d",&m,&n);    while (scanf("%d%d",&a,&b)&&(a!=-1&&b!=-1))        g[a][b]=g[b][a]=1;    memset(match,-1,sizeof match);    int cnt=0;    for (int i=1;i<=n-m;i++){        memset(vis,0,sizeof vis);        if (dfs(i+m))            cnt++;    }    printf(“%d\n”,cnt);    return 0;}

最小割

最大流和最小割是密不可分的。

最小割问题模型：

给定源点和汇点，有一张有向图，每条边有一定的权值。

现在要求你去掉一些边，是的源点到达汇点不存在路径，问至少要去掉多少权值的边。

看起来好难。

但是我们有：

最小割 = 最大流

怎么做？把权值看作容量，跑一跑网络流就可以了。

为什么？博主大蒟蒻也很菜的，也许给不出好的证明。

先引用一段证明：

来自算法导论

对于一个网络流图G=(V,E)，其中有源点s和汇点t，那么下面三个条件是等价的：
1. 流f是图G的最大流
2. 残留网络Gf不存在增广路
3. 对于G的某一个割(S,T)，此时f = C(S,T)
首先证明1 => 2：

我们利用反证法，假设流f是图G的最大流，但是残留网络中还存在有增广路p，其流量为fp。则我们有流f'=f+fp>f。这与f是最大流产生矛盾。
接着证明2 => 3：

假设残留网络Gf不存在增广路，所以在残留网络Gf中不存在路径从s到达t。我们定义S集合为：当前残留网络中s能够到达的点。同时定义T=V-S。
此时(S,T)构成一个割(S,T)。且对于任意的u∈S,v∈T，有f(u,v)=c(u,v)。若f(u,v)<c(u,v)，则有Gf(u,v)>0，s可以到达v，与v属于T矛盾。
因此有f(S,T)=Σf(u,v)=Σc(u,v)=C(S,T)。
最后证明3 => 1：

由于f的上界为最小割，当f到达割的容量时，显然就已经到达最大值，因此f为最大流。
这样就说明了为什么找不到增广路时，所求得的一定是最大流。