Dinic常规板子

// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define xx first
#define yy second
// #define ls u * 2
// #define rs u * 2 + 1
// #define int long long
using namespace std;
using ll = long long;
using ld = long double;
using PII = pair<int, int>;
const int N = 5e4 + 7, M = 3e5 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 1e17;
const double eps = 1e-10;
const ll mod = 1e9+7;

int n, m, s, t, maxflow;
int head[N], ver[M], nxt[M], edge[M], tot;
int d[N], now[N];
queue<int> q;

void add(int x, int y, int w) {
    ver[++ tot] = y, edge[tot] = w; nxt[tot] = head[x], head[x] = tot;
}

bool bfs() {
    while (q.size()) q.pop();
    memset(d, 0, sizeof d);
    q.push(s); d[s] = 1; now[s] = head[s];
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (edge[i] && !d[y]) {
                d[y] = d[x] + 1;
                now[y] = head[y];
                q.push(y);
                if (y == t) return 1;
            }
        }
    }
    return 0;
}

int dinic(int x, int flow) {
    if (x == t) return flow;
    int rest = flow;
    for (int i = now[x]; i && rest; i = nxt[i]) {
        now[x] = i;
        if (edge[i] && d[ver[i]] == d[x] + 1) {
            int k = dinic(ver[i], min(rest, edge[i]));
            if (!k) d[ver[i]] = 0;
            edge[i] -= k;
            edge[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;

}

void solve() {
    cin >> n >> m >> s >> t;
    tot = 1;
    for (int i = 1; i <= m; i ++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, 0);
    }
    int flow = 0;
    while (bfs())
        while (flow = dinic(s, inf)) maxflow += flow;
    cout << maxflow << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt --) solve();
    return 0;
}