题解：P3376 【模板】网络最大流

· · 题解

P3376 【模板】网络最大流

最大流算法：

引入：可以理解为有一个自来水厂要运水,每个管道最大通过的流量为 w_i。

实现：可以通过 BFS 找一条新路线直到没得找了,每次找到新路线计算最大流。

容量约束‌：因为通过的流量不能大于 w_i 所以当前路径的最大流不能大于当前路径里最小的边权。

反悔：为了解决错误的路径选择,所以允许流量回流,允许返回。

核心逻辑：通过不断寻找并利用‌增广路径‌来逐步增加总流量,直到无法找到新的增广路径为止。

题目概述

题目大意：计算从点 s 到点 t 的最大流。

算法思路：

‌残留网络：通过维护一个容量矩阵 cap_{i,j}，记录每条边的剩余容量。

路径：每次用 bfs 寻找一条从源点到汇点的路径,且每条路径上都有剩余的容量。

流量更新：计算路径上的最小容量 d,沿着正向边减去 d,再沿着反向边增加 b,因为允许反悔也就是流量回流。

结束条件：当没有办法找到其他的增广路线时,当前累计的流量为最大流。

代码解析：

BFS部分：

ll bfs(ll s, ll t) {
    memset(pre, -1, sizeof(pre));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && cap[now][i] > 0) {
                vis[i] = 1;
                pre[i] = now;  // 记录前驱节点
                if (i == t) return 1;
                q.push(i);
            }
        }
    }
    return 0;
}

功能：通过 BFS 找一条从 s 到 t 的路径。

计算最大流：

ll wll(ll s, ll t) {
    ll v, u, d, mfw = 0;
    while (bfs(s, t)) {  // 循环寻找增广路径
        v = t;
        d = 1e8;
        while (v != s) {  // 计算路径最小剩余容量
            u = pre[v];
            d = min(d, cap[u][v]);
            v = u;
        }
        mfw += d;
        v = t;
        while (v != s) {  // 更新残留网络
            u = pre[v];
            cap[u][v] -= d;
            cap[v][u] += d;// 处理反向边
            v = u;
        }
    }
    return mfw;
}

功能：累加每条路径的流量,更新残余流量。

整体代码：

如果看不懂上文可以看看注释

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, m, x, t;      // n:节点数 m:边数 x:源点 t:汇点
ll a, b, c;         // 临时变量用于输入边信息
ll cap[5010][5010]; // cap[u][v]表示u->v的剩余容量
ll pre[100000];     // 用于BFS找增广路径
ll vis[100000];     // 防止重复访问

ll bfs(ll s, ll t) {
    memset(pre, -1, sizeof(pre));   // 初始化为-1
    memset(vis, 0, sizeof(vis));   
    queue<int> q;
    vis[s] = 1;                     // 标记源点已访问
    q.push(s);

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        // 遍历所有可能的邻接点
        for (int i = 1; i <= n; i++) {
            // 存在剩余容量且未访问过
            if (!vis[i] && cap[now][i] > 0) {
                vis[i] = 1;
                pre[i] = now;       // 记录前驱节点
                if (i == t) return 1; // 找到汇点，立即返回
                q.push(i);
            }
        }
    }
    return 0; // 未找到增广路径
}

ll wll(ll s, ll t) {
    ll v, u, d, mfw = 0; // 最大流累计值
    // 每次寻找一条增广路径
    while (bfs(s, t)) {
        v = t;
        d = 100000000;   // 初始化为极大值
        // 回溯路径找最小剩余容量
        while (v != s) {
            u = pre[v];
            d = min(d, cap[u][v]); // 找路径上的瓶颈容量
            v = u;
        }
        mfw += d; // 累计到总流量

        // 更新残留网络
        v = t;
        while (v != s) {
            u = pre[v];
            cap[u][v] -= d; // 减少正向边容量
            cap[v][u] += d; // 增加反向边容量（允许回流）
            v = u;
        }
    }
    return mfw;
}

signed main() {

    std::ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> m >> x >> t;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        cap[a][b] += c; // 处理重边：直接累加容量
    }

    ll al = wll(x, t);
    cout << al;

    return 0;
}

谢谢观看