Dinic

#include <bits/stdc++.h>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

class FlowEdge {
    public:
        int u, v, capacity;

        FlowEdge(int u, int v, int capacity) {
            this -> u = u;
            this -> v = v;
            this -> capacity = capacity;
        }
};

class Dinic {
    public:
        const int INF = 0x3f3f3f3f;
        vector < FlowEdge > edges;
        vector < vector < int > > adj;
        int N, M = 0, source, sink;
        vector < int > level, ptr;
        queue < int > Q;

        Dinic(int N, int source, int sink) {
            this -> N = N;
            this -> source = source;
            this -> sink = sink;
            adj.resize(N + 1);
            level.resize(N + 1);
            ptr.resize(N + 1);
        }

        void add_edge(int u, int v, int capacity) {
            edges.emplace_back(u, v, capacity);
            edges.emplace_back(v, u, 0);
            adj[u].emplace_back(M++);
            adj[v].emplace_back(M++);
        }

        bool BFS() {
            while(!Q.empty()) {
                int curr = Q.front();
                Q.pop();
                for(int id : adj[curr])
                    if(level[edges[id].v] == -1 && edges[id].capacity) {
                        level[edges[id].v] = level[curr] + 1;
                        Q.emplace(edges[id].v);
                    }
            }
            return level[sink] != -1;
        }

        int DFS(int u, int curr_flow) {
            if(curr_flow == 0)
                return 0;
            if(u == sink)
                return curr_flow;
            for(int& p = ptr[u]; p < (int)adj[u].size(); ++p) {
                int id = adj[u][p],
                    v = edges[id].v;
                if(level[u] + 1 != level[v] || edges[id].capacity <= 0)
                    continue;
                int new_flow = DFS(v, min(curr_flow, edges[id].capacity));
                if(new_flow == 0)
                    continue;
                edges[id].capacity -= new_flow;
                edges[id ^ 1].capacity += new_flow;
                return new_flow;
            }
            return 0;
        }

        int max_flow() {
            int flow_max = 0;
            while(true) {
                fill(level.begin(), level.end(), -1);
                level[source] = 0;
                Q.emplace(source);
                if(!BFS())
                    break;
                fill(ptr.begin(), ptr.end(), 0);
                while(int curr_flow = DFS(source, INF))
                    flow_max += curr_flow;
            }
            return flow_max;
        }
};

int main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int N, M;
    fin >> N >> M;
    Dinic Graph(N, 1, N);
    while(M--) {
        int u, v, capacity;
        fin >> u >> v >> capacity;
        Graph.add_edge(u, v, capacity);
    }
    fout << Graph.max_flow();
}