Симплекс

#include <bits/stdc++.h>
using long_type = long long;
#define long long_type
#define all(x) begin(x), end(x)
using namespace std;

const int   max_n       = 1 << 17;
const int   int_inf     = 0x3f3f3f3f;
const long  long_inf    = 0x3f3f3f3f3f3f3f3f;
const int   source      = max_n - 1;
const int   sink        = max_n - 2;

struct edge {
    long c, f;
    int u, r;
    edge(int _u, long _c, int _r) :
        c(_c),
        f(0),
        u(_u),
        r(_r) {}
};

struct flow {
    long lim;
    int ptr[max_n], dist[max_n];
    vector<edge> g[max_n];
    void add_edge(int v, int u, long w) {
        assert(v != u);
        g[v].emplace_back(u, w, (int)g[u].size());
        g[u].emplace_back(v, 0, (int)g[v].size() - 1);
    }
    bool bfs() {
        fill(all(ptr), 0);
        fill(all(dist), int_inf);
        queue<int> q;
        q.push(source);
        dist[source] = 0;
        while (q.size()) {
            int v = q.front();
            q.pop();
            for (edge e : g[v]) {
                if (e.c - e.f >= lim && dist[e.u] > dist[v] + 1) {
                    dist[e.u] = dist[v] + 1;
                    q.push(e.u);
                }
            }
        }
        return dist[sink] < int_inf;
    }
    long dfs(int v, long mn) {
        if (v == sink) {
            return mn;
        }
        for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
            edge &e = g[v][ptr[v]];
            edge &r = g[e.u][e.r];
            if (dist[e.u] != dist[v] + 1 || e.c - e.f < lim) {
                continue;
            }
            long d = dfs(e.u, min(mn, e.c - e.f));
            if (d) {
                e.f += d;
                r.f -= d;
                return d;
            }
        }
        return 0;
    }
    long max_flow() {
        long sum = 0;
        for (lim = 1; lim >= 1; lim >>= 1) {
            while (bfs()) {
                long cur = dfs(source, long_inf);
                while (cur) {
                    sum += cur;
                    cur = dfs(source, long_inf);
                }
            }
        }
        return sum;
    }
} f;


int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
//~ #define TASK "maxflow"
    //~ assert(freopen(TASK ".in", "r", stdin));
    //~ assert(freopen(TASK ".out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    while (m--) {
        int v, u, w;
        cin >> v >> u >> w;
        f.add_edge(v, u, w);
    }
    f.add_edge(source, 1, long_inf);
    f.add_edge(n, sink, long_inf);
    cout << f.max_flow() << "\n";
    cerr << 1000 * clock() / CLOCKS_PER_SEC << endl;
    return 0;
}