Zabk's Blog

Appearance

Home/Articles/网络流

DeepSeek Chat

Problem ​

有向图N=(V,E)N=(V,E): 每个边都有最大流量cc
求起点s到终点t的最大流量 fstf_{st}

从点i到点j的边：
fijf_{ij}: 可行流
cijc_{ij}: 最大流
0<f<c0 \lt f \lt c

Solution ​

一直寻找增广路，直到没有

前向流：沿着边的方向
后向流：逆着边的方向
前向弧和后相弧可以相互抵消
最终形成正确的路径

类似于反悔自动机？

标号法 ​

BFS
先找一条路
再找下一条路

Dinic ​

  1. 双向建边
    边权为剩余流量
  2. bfs标出depth
  3. 循环dfs直到增广流为0
    • 前向流边权+w,后向流边权-w

当前弧优化 ​

当前弧优化（Current Arc Optimization）是 Dinic 算法（一种求解最大流的常用算法）中一个经典且高效的优化技巧。它通过避免在每次 DFS 寻找增广路时重复扫描已经"无用"的边，大大加速了算法的整体运行速度。

1. 为什么需要当前弧优化？ ​

在 Dinic 算法的每次 BFS 构建完分层图（dep graph）后，我们反复执行 DFS 从源点到汇点寻找增广路。
在 DFS 过程中，对于某个节点 u，我们会遍历其所有的出边（按邻接表顺序），尝试找到一条容量大于 0 且指向下一层（dep[v] == level[u] + 1）的边 (u, v)，然后递归推流。

问题在于：

  • 一旦某条边 (u, v) 的剩余容量变为 0（即被完全使用），在当前 BFS 阶段内它不可能再运送更多流量，因此后续的 DFS 无需再查看它。
  • 如果从某条边出发无法推流（例如下游节点无法再增广），那么这条边在当前分层图中也"失效"了，后续 DFS 也可以跳过它。

如果没有优化，每次 DFS 都会从每个节点的第一条边开始重新扫描，导致大量的重复检查，尤其当图很大时，时间复杂度会退化。

2. 当前弧优化的核心思想 ​

为每个节点维护一个指针（或称"迭代器"），指向其邻接表中下一条应该尝试的边。在同一个 BFS 阶段内，当一条边被判定为"暂时无用"后，我们就将指针向后移动，从而在后续的 DFS 中直接跳过它，不再重复判断。

注意：每个 BFS 阶段（即分层图重建）之后，所有指针需要重置回起点，因为新的分层图可能使之前"无用"的边重新变得可用。

3. 具体实现方式 ​

通常使用一个数组 cur[]（或 it[]），大小等于顶点数。
在每次 BFS 之后，将 cur[u] 初始化为 0（或邻接表起始下标）。

在 DFS 函数中，对于节点 u，我们不再从 0 开始遍历，而是从 cur[u] 开始：

cpp
int dfs(int u, int t, int f) {
    if (u == t) return f;
    for (int &i = cur[u]; i < (int)g[u].size(); ++i) {
        Edge &e = g[u][i];
        if (e.cap > 0 && dep[e.to] == level[u] + 1) {
            int pushed = dfs(e.to, t, min(f, e.cap));
            if (pushed) {
                e.cap -= pushed;
                g[e.to][e.rev].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

关键点：

  • int &i = cur[u] 表示 i 是 cur[u] 的引用，修改 i 会改变指针值。
  • 当循环进行时，i 不断递增，如果某条边无法增广，则 i 会自增，从而"跳过"它。
  • 只有当 DFS 成功推流时，才返回（不修改 cur[u]，因为该边可能还有剩余容量，下次还可以继续使用）。如果后续该边也被耗尽，则在下次 DFS 时会自动被跳过。
4. 效果与复杂度 ​

有当前弧优化O(V²E)

Example ​

Luogu P2740

cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Edge {
    int to, rev;
    ll cap;
};

int N, M;          // N = 边数, M = 点数
vector<vector<Edge>> g;
vector<int> dep, it;

// BFS 构建分层图
bool bfs(int s, int t) {
    fill(dep.begin(), level.end(), -1);
    queue<int> q;
    dep[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (const Edge &e : g[u]) {
            if (e.cap > 0 && dep[e.to] == -1) {
                dep[e.to] = level[u] + 1;
                q.push(e.to);
            }
        }
    }
    return dep[t] != -1;
}

// DFS 推送流量（带当前弧优化）
ll dfs(int u, int t, ll f) {
    if (u == t) return f;
    for (int &i = it[u]; i < (int)g[u].size(); ++i) {
        Edge &e = g[u][i];
        if (e.cap > 0 && dep[e.to] == level[u] + 1) {
            ll pushed = dfs(e.to, t, min(f, e.cap));
            if (pushed > 0) {
                e.cap -= pushed;
                g[e.to][e.rev].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

ll max_flow(int s, int t) {
    ll flow = 0;
    while (bfs(s, t)) {
        fill(it.begin(), it.end(), 0);
        while (true) {
            ll pushed = dfs(s, t, INF);
            if (!pushed) break;
            flow += pushed;
        }
    }
    return flow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    g.assign(M + 1, {});
    dep.assign(M + 1, -1);
    it.assign(M + 1, 0);

    for (int i = 0; i < N; ++i) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        // 有向边：正向容量 c，反向容量 0
        g[u].push_back({v, (int)g[v].size(), c});
        g[v].push_back({u, (int)g[u].size() - 1, 0});
    }

    cout << max_flow(1, M) << '\n';
    return 0;
}
Download Markdown