网络流

概念讲解

核心概念

最大流

从 s 到 t 的最大流量。

Edmonds-Karp 算法

思路

每次用 BFS 找增广路，更新残量网络。

代码

123456789101112131415161718192021222324252627282930313233343536int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    queue<pair<int,int>> q;
    q.push({s, 1e9});
    parent[s] = s;
    
    while (!q.empty()) {
        auto [u, flow] = q.front();
        q.pop();
        for (int v = 1; v <= n; v++) {
            if (parent[v] == -1 && cap[u][v] > 0) {
                int newFlow = min(flow, cap[u][v]);
                parent[v] = u;
                if (v == t) return newFlow;
                q.push({v, newFlow});
            }
        }
    }
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    vector<int> parent(n+1);
    int newFlow;
    while ((newFlow = bfs(s, t, parent)) > 0) {
        flow += newFlow;
        int cur = t;
        while (cur != s) {
            cap[parent[cur]][cur] -= newFlow;
            cap[cur][parent[cur]] += newFlow;
            cur = parent[cur];
        }
    }
    return flow;
}

最小割

最大流最小割定理： 最大流 = 最小割

考点分析

初赛考查方式

1. 程序阅读： 网络流
2. 编程题： 最大流

常见考点

• 最大流
• 最小割
• 二分图匹配

练习题

1. 最大流最小割定理是什么？

2. EK 算法的时间复杂度是多少？

3. 如何用网络流解决二分图匹配？

易错点

⚠️ 注意：

1. 要维护残量网络
2. 反向边很重要
3. Dinic 比 EK 更快
4. 网络流是高级内容