EK算法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1010, M = 20010;
const int inf = 0x3f3f3f3f;
int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, maxflow, pre[N], incf[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}
// 找一条增广路
bool bfs()
{
    memset(st, false sizeof st);
    queue <int> q;
    q.push(S);
    st[S] = true;
    incf[S] = inf; // 从源点可以有无限量的水流出来
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int i = h[u]; i != -1; i = ne[i]){
            if(w[i]){     // 根据增广路的定义 只有当前边的容量大于 0
                int j = e[i];
                if(st[j])  continue;
                incf[j] = min(incf[u], w[i]);//一条增广路上流过的最大可行流受到每条边的最小容量限制
                pre[j] = i; // 记录当前点的前驱边
                q.push(j);
                st[j] = true;
                if(j == T)  return true;
            }
        }
    }
    return false;
}

// 更新残留网络
void update()
{
    int x = T;
    while(x != S){
        int i = pre[x];
        w[i] -= incf[T]; // c(u, v) 的容量减去找到的增广路上的最小容量
        w[i ^ 1] += incf[T]; // (u, v)的反向边加上找到的增广路上的最小容量
        x = e[i ^ 1]; 
    }
    maxflow += incf[T]; // 累加所有增广路的最大可行流
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);

    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, 0); // 正向边，反向边
    }

    while(bfs())    
      update();
    cout << maxflow << endl;

    return 0;
}

Dinic算法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, cur[N], d[N], q[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}
bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    d[S] = 0, q[0] = S, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            int j = e[i];
            if(w[i] && d[j] == -1){
                d[j] = d[u] + 1;
                cur[j] = h[j];
                if(j == T)   return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}
// 更新残留网络
int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i; // 当前弧优化
        int j = e[i];
        if(w[i] && d[j] == d[u] + 1){
            int k = dfs(j, min(flow - rest, w[i]));
            if(k == 0)  d[j] = -1; // 3号优化，将分层图中的当前点变成 -1 相当于打上标记
            w[i] -= k, w[i ^ 1] += k, rest += k;
            if(rest == flow)    return flow; // 2号优化
        }
    }
    return rest;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())    
      while(flow = dfs(S, inf))  
       res += flow;
    return res;
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, 0);
    }

    printf("%d\n", dinic());

    return 0;
}