首页 > 编程学习 > 【算法学习笔记】05 网络流

【算法学习笔记】05 网络流

发布时间:2022/8/26 11:49:30

【算法学习笔记】05 网络流

入个大坑

1. 基本概念

1.1 流网络

不考虑反向边
记图为 \(G=(V,E)\)
有一个源点 \(S\) 和汇点 \(T\)

1.2 可行流

不考虑反向边

1.2.1 条件

容量限制:\(0\leq f(u,v)\leq C(u,v)\)

流量守恒:中间点不储存流量

\[\sum_{(v,x)\in E}f(v,x)=\sum_{(x,v)\in E}f(x,v) \]

1.2.2 流量值

\[f=\sum_{(s,v)\in E}f(s,v)-\sum_{(v,s)\in E}f(v,s) \]

流出 - 流入

1.2.3 最大流

最大可行流

1.3 残留网络

考虑反向边

\(G_f,\) 由可行流决定,\(V_f=V,E_f=E+E\) 中所有反向边,即

\[C'(u,v)= \begin{cases} C(u,v)-f(u,v),& (u,v)\in E\,(增流)\\ f(v,u), & (v,u)\in E\,(退回去)\\ \end{cases} \]

\(|f|+|f'|=|f+f'|:\) 原图的可行流\(f+\)残留网络的可行流\(f'=\) 原图的另一个可行流

1.4 增广路径

残量网络中,沿着流量 \(>0\) 的边走可以走到终点的路径

1.5 割

1.5.1 定义

把所有点不重不漏的分为两个集合 \(S,T\), 即

源点 \(\in S\), 汇点 \(\in T\), 且 \(S \cap T=\emptyset,S\cup T=V\)

1.5.2 割的容量

不考虑反向边
\(S\rightarrow T\)

\[c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v) \]

1.5.3 割的流量

考虑反向边
\(S\rightarrow T-T\rightarrow S\)

\[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)\leq c(S,T)\)

1.5.4

对于任意可行流 \(f\), 任意割 \([S,T]\), \(|f|=f(S,T)\)

1.5.5

对于任意可行流 \(f\), 任意割 \([S,T]\), \(|f|\leq c(S,T)\)

1.5.6 最大流最小割定理

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

1.6 算法

1.6.0 FF思想

维护残留网络
每次:找增广路 + 更新残留网络(正向\(+k\), 反向\(-k\)
存图:邻接表,正反向边成对存储

1.6.1 \(EK\) 算法

#include <bits/stdc++.h>

using namespace std;
const int N = 1005, M = 10005 * 2, inf = 1e9;
int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx;
bool vis[N];
int d[N], pre[N];

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool bfs () {
    queue<int> q;
    memset (vis, false, sizeof vis);
    memset (d, 0, sizeof d);
    memset (pre, 0, sizeof pre);
    q.push (S), vis[S] = true, d[S] = inf;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (vis[j] || w[i] == 0)    continue;
            pre[j] = i;
            vis[j] = true;
            d[j] = min (d[t], w[i]);

            if (j == T) return true;
            q.push (j);
        }
    }
    return false;
}

int EK () {
    int ans = 0;
    while (bfs ()) {
        ans += d[T];
        for (int i = T; i != S; i = e[pre[i]^1]) {
            w[pre[i]] -= d[T], w[pre[i]^1] += d[T];
        }
    }
    return ans;
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, 0);
    }
    cout << EK() << endl;
}

1.6.2 \(Dinic\) 算法

1.7 应用

1.7.1 二分图

1. 二分图匹配
2. 二分图多重匹配

1.7.2 上下界网络流

1. 无源汇上下界可行流
2. 有源汇上下界最大流
3. 有源汇上下界最小流

1.7.3 多源汇最大流

补充

  1. EK求最大流
  2. Pecco大大!
  3. ctx大佬的板子
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号