Dinic

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;

#define MAXV 5010
#define MAXE 30010

const int inf = 0x3f3f3f3f;
const long long llinf = 30000LL*100000000000LL;

struct edge {
    long long c,f;
    int src,dst,prev;
};

edge ls[2*MAXE];
int lastEdge[MAXV];
int currEdge[MAXV];
int d[MAXV];
int n,m;
int s,t;
queue<int> q;

void makeEdge(int idx, int a, int b, int c) {
    ls[idx].prev=lastEdge[a];
    lastEdge[a]=idx;
    ls[idx].dst=b, ls[idx].src=a;
    ls[idx].c=c, ls[idx].f=0LL;
}

bool bfs() {
    memset(d,0x3f,sizeof(d));
    q.empty();

    for (int i=0; i<n; i++)
        currEdge[i]=lastEdge[i];

    q.push(s);
    d[s]=0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i=lastEdge[u]; i!=-1; i=ls[i].prev)
            if (ls[i].c-ls[i].f>0 && d[ls[i].dst]==inf) {
                int v=ls[i].dst;
                d[v]=d[u]+1;
                q.push(v);
            }
    }

    return d[t]!=inf;
}

long long dfs(int u, long long flow) {
    if (u==t) return flow;

    for (int& i=currEdge[u]; i!=-1; i=ls[i].prev) {
        if (d[ls[i].dst]!=d[u]+1 || (ls[i].c-ls[i].f==0))
            continue;

        long long tmpF = dfs(ls[i].dst, min(flow,ls[i].c-ls[i].f));

        if (tmpF) {
            ls[i].f+=tmpF;
            ls[i^1].f-=tmpF;
            return tmpF;
        }
    }

    return 0LL;
}

long long dinic() {
    long long maxFlow=0;

    while (bfs()) {
        long long flow=0;
        while (flow=dfs(s,llinf))
            maxFlow+=flow;
    }

    return maxFlow;
}

int main() {
    scanf("%d %d", &n,&m);
    memset(lastEdge,-1,sizeof(lastEdge));
    s=0, t=n-1;

    for (int i=0; i<m; i++) {
        int a,b,c;
        scanf("%d %d %d", &a,&b,&c);
        a--, b--;

        makeEdge(2*i,a,b,c);
        makeEdge(2*i+1,b,a,c);
    }

    printf("%lld\n", dinic());
    return 0;
}