图论 -- 网络流最大流问题

问题表述：给定一幅图（n 个结点，m 条边），每一条边有一个容量，现在需要将一些物品从结点 s（称为源点）运送到结点 t（称为汇点），可以从其他结点中转，求最大的运送量。

在介绍最大流问题的解决方法之前，先介绍几个概念.

网络：网络是一个有向带权图，包含一个源点和一个汇点，没有反向平行边。

网络流：网络流即网上的流，是定义在网络边集 E 上的一个非负函数 flow={flow（u，v）}, flow（u,v）是边上的流量。

可行流：满足以下两个性质的网络流 flow 称为可行流。

容量约束：每条边的实际流量不能超过改变的最大流量。

流量守恒：除了源点 s 和汇点 t 之外，所有内部节点流入量等于流出量。

源点 s：源点主要是流出，但也有可能流入。

源点的净输出值=流出量之和-流入量之和。

汇点 t：汇点主要是流入，但也有可能流出。

汇点的净输入值=流入量之和-流出量之和。

对于一个网络可行流 flow，净输出等于净输入，这仍然是流量守恒。

网络最大流：在满足容量约束和流量守恒的前提下，在流网络中找到一个净输出最大的网络流。

反向弧：若从 u 到 v 的边的容量为 c ，这条边上有流量 f 流过（称为正向弧），则相当于 v 到 u 有一条容量为 0 的边，其流量为- f ，这条边就是反向弧。反向弧的作用主要是用于寻找增广路。

反向弧的意义：反向弧的作用是起到有更优决策的时候会使当前选择的弧会自动放弃。反向弧有流量的原因是因为如果刚刚选择了正向弧，下一次如果存在更优策略使这 f 的流量流入汇点，就可以选择反向弧，将流量 f 撤销。

残余网络：计算出图中的每条边上容量与流量之差（称为残余容量），即可得到残余网络。注意由于反向边的存在，残余网络中的边数可能到达原图中边数的两倍。

观察图下图，这种状态下它的残余网络。

​

增广路径：残余网络中任何一条从 s 到 t 的有向道路都对应一条原图中的增广路径 —— 只要求出该道路中所有残量的最小值 d ，把对应的所有边上的流量增加 d 即可，这个过程称为增广。

最大流定理：如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。

这样的话，求解最大流就只需要在残余网络中寻找增广路，直到不存在可以从 s 流向 t 的增广路，此时即为最大流。求解最大流问题的高效算法有 dinic,sap 和 isap。

我们今天讲最基础的 FF 算法与 EK 算法，他俩的区别在于一个是 DFS 找增广路，一个是 BFS 找增广路。后者高效一点。

Edmonds-Karp 算法：以广度优先的增广路算法，又称为最短增广路算法（Shortest Augument Panth, SAP）。

最短增广路算法步骤：采用队列 q 来存放已访问未检查的结点。布尔数组 vis[]标识结点是否被访问过，pre[]数组记录可增广路上结点的前驱。pre[v]=u 表示可增广路上 v 结点的前驱是 u，最大流值 maxflow=0。

1. 初始化可行流 flow 为零流，即实流网络中全是零流边，残余网络中全是最大容量边（可增量）。初始化 vis[]数组为 false，pre[]数组为−1。

2. 令 vis[s]=true，s 加入队列 q。

3. 如果队列不空，继续下一步，否则算法结束，找不到可增广路。当前的实流网络就是最大流网络，返回最大流值 maxflow。

4. 队头元素 new 出队，在残余网络中检查 new 的所有邻接结点 i。如果未被访问，则访问之，令 vis[i]=true，pre[i]=new；如果 i=t，说明已到达汇点，找到一条可增广路，转向第（5）步；否则结点 i 加入队列 q，转向第（3）步。

5. 从汇点开始，通过前驱数组 pre[]，逆向找可增广路上每条边值的最小值，即可增量 d。

6. 在实流网络中增流，在残余网络中减流，Maxflow+=d，转向第（2）步。

 这里给出 EK 算法模板：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#define INF 0x3f3f3f3fusing namespace std;int n,m;const int maxn=1005;int g[maxn][maxn];//容量int f[maxn][maxn];//流量bool vis[maxn];int pre[maxn];bool bfs(int s,int t){    memset(pre,-1,sizeof pre);    memset(vis,false,sizeof vis);    queue<int> q;    vis[s]=true;    q.push(s);    while(!q.empty()){        int now=q.front();        q.pop();        for(int i=1;i<=n;i++){            if(!vis[i]&&g[now][i]){                vis[i]=true;                pre[i]=now;                if(i==t) return true;                q.push(i);            }        }    }    return false;}int EK(int s,int t){    int maxflow=0;    int u,v;    while(bfs(s,t)){        int d=INF;        v=t;        while(v!=s){            u=pre[v];            if(d>g[u][v])                d=g[u][v];            v=u;        }        maxflow+=d;        v=t;        while(v!=s){            u=pre[v];            g[u][v]-=d;            g[v][u]+=d;            if(f[v][u]>0)                f[v][u]-=d;            else f[u][v]+=d;            v=u;        }    }    return maxflow;}int main(){    //int s,t;    int u,v,c;    while(~scanf("%d%d",&m,&n)){        memset(f,0,sizeof f);        memset(g,0,sizeof g);        for(int i=1;i<=m;i++){            scanf("%d%d%d",&u,&v,&c);            g[u][v]+=c;        }        printf("%d\n",EK(1,n));    }    return 0;}

点击并拖拽以移动