0w1

Template Dinic

Given N nodes, M arcs, returns max flow from 0 to N.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< int, ll > pil;
typedef pair< ll, int > pli;
typedef pair< ll, ll > pll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector< double > vd;
typedef vector< vd > vvd;
typedef vector< pii > vp;
typedef vector< vp > vvp;
typedef vector< bool > vb;
typedef vector< vb > vvb;

template< class T1, class T2 >
bool upmin( T1 &x, T2 v ){
    if( x > v ){
        x = v;
        return true;
    }
    return false;
}

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
    if( x < v ){
        x = v;
        return true;
    }
    return false;
}

const int INF = 0x3f3f3f3f;

struct Nedge{ // network edge
    int from, to, cap, flow;
    Nedge(){}
    Nedge( int _f, int _t, int _c, int _fl ){
        from = _f;
        to = _t;
        cap = _c;
        flow = _fl;
    }
};

struct Dinic{
    int n, m, s, t;
    vector< Nedge > edge;
    vvi G;
    vb vis;
    vi dis;
    vi cur;
    Dinic( int sz ){
        n = sz;
        edge.clear();
        G.clear(); G.resize( sz );
        vis.clear(); vis.resize( sz );
        dis.clear(); dis.resize( sz );
        cur.clear(); cur.resize( sz );
    }
    void add_edge( int from, int to, int cap ){
        edge.push_back( Nedge( from, to, cap, 0 ) );
        edge.push_back( Nedge( to, from, 0, 0 ) );
        m = edge.size();
        G[ from ].push_back( m - 2 );
        G[ to ].push_back( m - 1 );
    }
    bool BFS(){
        fill( vis.begin(), vis.end(), 0 );
        queue< int > que;
        que.push( s );
        dis[ s ] = 0;
        vis[ s ] = 1;
        while( not que.empty() ){
            int x = que.front(); que.pop();
            for( int i = 0; i < G[ x ].size(); ++i ){
                Nedge &e = edge[ G[ x ][ i ] ];
                if( not vis[ e.to ] and e.cap > e.flow )
                    vis[ e.to ] = 1,
                    dis[ e.to ] = dis[ x ] + 1,
                    que.push( e.to );
            }
        }
        return vis[ t ];
    }
    int DFS( int x, int a ){
        if( x == t or a == 0 ) return a;
        int flow = 0, f;
        for( int &i = cur[ x ]; i < G[ x ].size(); ++i ){ // so that cycles won't matter, know what I mean?
            Nedge &e = edge[ G[ x ][ i ] ];
            if( dis[ x ] + 1 == dis[ e.to ] and ( f = DFS( e.to, min( a, e.cap - e.flow ) ) ) > 0 ){
                e.flow += f;
                edge[ G[ x ][ i ] ^ 1 ].flow -= f;
                flow += f;
                a -= f;
                if( a == 0 ) break;
            }
        }
        return flow;
    }
    int max_flow( int s, int t ){
        this->s = s; this->t = t;
        int flow = 0;
        while( BFS() )
            fill( cur.begin(), cur.end(), 0 ),
            flow += DFS( s, INF );
        return flow;
    }
};

void solve(){
    int N, M; cin >> N >> M;
    Dinic *din = new Dinic( N );
    for( int i = 0; i < M; ++i ){
        int u, v, c; cin >> u >> v >> c;
        din->add_edge( u - 1, v - 1, c );
    }
    cout << din->max_flow( 0, N - 1 ) << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    solve();
    return 0;
}