---
title: "网络流"
cato: oi
time: "2026-07-06"
---

[DeepSeek Chat](https://chat.deepseek.com/a/chat/s/34d51cc0-978b-44bf-9626-1c7cfc91ee04)

## Problem

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

从点i到点j的边：  
$f_{ij}$: 可行流  
$c_{ij}$: 最大流  
$0 \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](https://www.luogu.com.cn/problem/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;
}
```