【模板】网络流最大流

Phrink734 / 2024-08-18 / 原文

最大流

题目要求:给出n点 m边 src sink 然后每条边有 u v capacity 求最大流

题目链接P3376 【模板】网络最大流

EK(Edmonds–Karp)算法:

\[\begin{align} & \color{Red}时间复杂度O(nm^2) \\ & \color{Red}空间复杂度O(n+m) \\ \end{align} \]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define int long long 
const int N = 6e5 + 9;  
const int inf2 = 0x7f7f7f7f; 

using namespace std;
#define int long long
#define ios std::ios::sync_with_stdio(false); std::cin.tie(0); 

int n, m, src, sink; 
int ans = 0;          // 最大流量
int head[N];          
int pre[N];           // 存储前驱边的数组 即连接节点u的上一条egde
struct node {
    int to, capacity, next;  
} e[N];
bool vis[N];         
int idx = 1;         
int dist[N];         // 存储从源节点到各节点的最短路径流量
int flag[2510][2510]; // 用于标记边的索引

void add(int u, int v, int val) {
    // 添加正向边
    e[++idx] = {v, val, head[u]};
    head[u] = idx;
    // 添加反向边
    e[++idx] = {u, 0, head[v]};
    head[v] = idx;
}

bool bfs() {
    memset(vis, 0, sizeof vis); // 清空访问标记数组
    dist[src] = inf2; // 初始化源节点的距离为无穷大
    queue<int> q;
    q.push(src);
    vis[src] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != 0; i = e[i].next) {
            int v = e[i].to;
            int val = e[i].capacity;
            // 如果边的容量为 0 或节点 v 已访问，跳过
            if (e[i].capacity == 0 || vis[v]) continue;
            vis[v] = 1;
            pre[v] = i; // 记录前驱边
            dist[v] = min(dist[u], val); // 流量只能取得最小的
            q.push(v); 
            if (v == sink) // 到达sink，返回 true
                return true;
        }
    }
    return false; // 没有找到增广路径
}

void EK() {
    int u = sink;
    while (u != src) {
        int mmin_stream = dist[sink]; // 当前增广路径的流量是整条路的最小值
        int last = pre[u]; 
        // 更新正向边的容量和反向边的容量
        e[last].capacity -= mmin_stream;
        e[last ^ 1].capacity += mmin_stream;
        u = e[last ^ 1].to; // 更新 u 为反向边的终点
    }
    ans += dist[sink]; // 增加当前流量到总流量
}

void bd() {
    cin >> n >> m >> src >> sink;
    for (int i = 1; i <= m; ++i) {
        int u, v, val;
        cin >> u >> v >> val; 
        if (flag[u][v] == 0) {
            add(u, v, val); // 添加边到图中
            flag[u][v] = idx - 1; // 记录边的索引 因为dix起步时=1
        } 
        else 
            e[flag[u][v]].capacity += val; 
            //存在多条边 容量加起来
    }
}

signed main() {
    ios;
    bd(); 
    while (bfs()) {
        EK();
    }
    cout << ans; // 输出最大流量a
    return 0;
}