图论 | 网络流的基本概念-Toy模板网

这篇具有很好参考价值的文章主要介绍了图论 | 网络流的基本概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

流网路

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

图论 | 网络流的基本概念,手撕算法,图论,网络,网络流

有向图，不考虑反向边
s：源点
t：汇点
$c (u, v)$ ：边的最大容量
可行流 $f$
- 容量限制： $\leq f(u, v) \leq 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^{'} ∣ = ∣ f ∣ + ∣ f^{'} ∣$
进一步，若残留网络没有可行流，那么原网络的可行流就一定是最大流

增广路径

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

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

割

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

分割要满足 $\emptyset$
点集不一定连通

割的容量： $\sum_{u ∈ S} \sum_{v ∈ T} c(u, v)$

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

割的流量： $\sum_{u ∈ S} \sum_{v ∈ T} f(u, v) - \sum_{u ∈ T} \sum_{v ∈ S} f(u, v)$

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

重要性质：

对于任意一个割，割的流量一定小于等于割的容量，即 $\leq 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)$

最大流最小割定理

以下三个条件是等价的

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

最大流

Edmonds-Karp 算法

算法步骤

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

找一条增广路 $f^{'}$ ：可以用 BFS 进行搜索
更新残留网络 $G_f → G_{f + f'}$

程序代码

#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++;
    // 反向边，初始容量为0
    e[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) {
        // 从队列中弹出一个元素进行BFS
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i]) {
            // 节点t的临接边i的下一节点ver
            int ver = e[i];
            // 没遍历过且边i的容量不为0
            if( !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的容量为c
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    cout << EK() << endl;
    return 0;
}