图论 | 网络流的基本概念

流网路

流网络：$G=(V,E)$

• 有向图，不考虑反向边
• s：源点
• t：汇点
• $c(u,v)$：边的最大容量
• 可行流 $f$
  • 容量限制：$0\le f(u,v)\le c(u,v)$
  • 流量守恒：除了源点和汇点，所有点满足 $流入=流出$
• $|f|$：可行流的流量，即从源点流向汇点的速率。一种通用的解释是 $从源点流出的流量-流入源点的流量$
• 最大流：最大可行流

残留网络

残留网络定义：一个可行流流网络 $f$ 对应一个残留网络 $G_f$

• 点集：与原图的点集一样 $V_f=V$
• 边集：不仅包含原图的边，同时包含所有边的方向边，即 $E_f=E和E中的所有反向边$
• 边的容量： $c_f(u,v)$
  • 原图中的边：剩下的容量，即 $c(u,v)-f(u,v)$
  • 反向边：可以退回的流量，即 $f(v,u)$

重要结论：原网络的可行流 $f$ 加上可行流对应的残留网络 $G_f$，也是一个可行流

• 对应边相加：若方向同则相加；若反向反则相减
• 结论：$|f+f^{\prime }|=|f|+|f^{\prime }|$
• 进一步，若残留网络没有可行流，那么原网络的可行流就一定是最大流

增广路径

在残留网络里，如果沿着容量大于 0 的边走，能走到汇点，则这条路径叫做增广路径

• 若存在一个增广路径，根据 $|f+f^{\prime }|=|f|+|f^{\prime }|$，原来的可行流一定不是最大流
• 若不存在增广路径，我们可以得出当前可行流就是最大流

割

将点集 V 分成 S 和 T 两个子集

• 分割要满足 $S\cup T=V，S\cap T=\varnothing$
• 点集不一定连通

割的容量：$c(S,T)={\sum }_{u\in S}{\sum }_{v\in T}c(u,v)$

• 最小割：最小割的容量
• 割的容量不考虑反向边

割的流量：$f(S,T)={\sum }_{u\in S}{\sum }_{v\in T}f(u,v)-{\sum }_{u\in T}{\sum }_{v\in S}f(u,v)$

• 流过去的流量减去流过来的流量
• 割的流量考虑反向边

重要性质：

• 对于任意一个割，割的流量一定小于等于割的容量，即 $f(S,T)\le c(S,T)$

• 割的流量等于原流网络的流量，即$f(S,T)=|f|$

• $f(X,Y)=-f(Y,X)$

• $f(Z,X\cup Y)=f(Z,X)+f(Z,Y)$

• $f(X\cup Y,Z)=f(X,Z)+f(Y,Z)$

最大流最小割定理

以下三个条件是等价的

1. 可行流 $f$ 是最大流
2. 可行流 $f$ 的残留网络中不存在增广路
3. 存在某个割 $[S,T]$，$|f|=c(S,T)$

最大流

Edmonds-Karp 算法

算法步骤

维护流网络的残留网络，不断进行以下流程：

1. 找一条增广路 $f^{\prime }$：可以用 BFS 进行搜索
2. 更新残留网络 $G_f\to G_{f+f^{\prime }}$

程序代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, M = 20020, INF = 1e8;// 邻接表存储残留网络
// 正向边和反向边成对存在，正向边的下标异或上1得到方向边的下标
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;  // f表示容量
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++;// 反向边，初始容量为0e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}// bfs找增广路
bool bfs()
{int hh = 0, tt = 0;memset(st, false, sizeof(st));q[0] = S, st[S] = true, d[S] = INF;while(hh <= tt) {// 从队列中弹出一个元素进行BFSint t = q[hh++];for(int i = h[t]; ~i; i = ne[i]) {// 节点t的临接边i的下一节点verint ver = e[i];// 没遍历过且边i的容量不为0if( !st[ver] && f[i] ) {st[ver] = true;// 流到节点ver的流量为流到t的流量和边i容量的最小值d[ver] = min(d[t], f[i]);// 记录节点ver前驱边的编号pre[ver] = i;if(ver == T)  return true;// ver入队q[++tt] = ver;}}}return false;
}// EK 算法
int EK()
{int r = 0;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];}}return r;
}int main()
{// 点数、边数、源点、汇点cin >> n >> m >> S >> T;// 初始化邻接表memset(h, -1, sizeof(h));while( m-- ) {int a, b, c;// 边ab的容量为ccin >> a >> b >> c;add(a, b, c);}cout << EK() << endl;return 0;
}

时间复杂度

$O(V{E}^2)$