Dinic Algorithm (2)

#include<bits/stdc++.h>
#define ll long long

// Alternative for Dinic
// Pros: support large number of vertices and edges
// Cons: Take longer time to run.
// Usage: 
//      Dinic dinic; 
//      dinic.init(n); 
//      dinic.addEdge(...); 
//      maxFlow = dinic.run(source, sink);
struct Dinic2 {

    struct Edge {
        int v; // the other-end of this edge
        ll c; // capacity
        ll flow; // current flow
        int rev; // index of the reverse-edge
            
    };
    
    int n;
    vector<Edge> *adj;
    int *dlevel;
    pair<int, int> *prev;
    int *visit;
    
    ll maxCapacity;
    
    Dinic2(){
        maxCapacity = 1ll * oo * oo;
    }
    
    void init(int n_) {
        n = n_;
        
        adj = new vector<Edge>[n+1];
        dlevel = new int[n+1];
        prev   = new pair<int, int> [n+1];
        visit  = new int[n+1];
        
        fill(dlevel, dlevel + n+1, 0);  
        fill(prev, prev + n+1, make_pair(0, 0));    
        fill(visit, visit + n+1, 0);    
    }
    
    void addEdge(int u, int v, int w) {
        
        Edge e1{v, w, 0, adj[v].size()};
        Edge e2{u, w, w, adj[u].size()};
        
        adj[u].push_back(e1);
        adj[v].push_back(e2);
        
    }
    
    bool constructLevel(int source, int sink) {
        fill(dlevel, dlevel + n+1, -1);
        dlevel[source] = 0;
        
        queue<int> que;
        que.push(source);
        
        while(!que.empty()) {
            int vertex = que.front();
            que.pop();
            
            for (int i = 0; i < adj[vertex].size(); ++i) {
                int next = adj[vertex][i].v;
                
                if (dlevel[next] >= 0)
                    continue;
                
                if (adj[vertex][i].c > adj[vertex][i].flow) {
                    que.push(next);
                    dlevel[next] = dlevel[vertex] + 1;
                }
                
            }
        }
        
        return dlevel[sink] >= 0;
    }
    
    ll makeFlow(int source, int sink) {
        
        ll ret = 0;
        
        fill(visit, visit + n+1, 0);
        
        stack<int> stk;
        stk.push(source);
        
        while(!stk.empty()) {
            
            int now = stk.top();
            
            if (now != sink) {
                
                for (int i = 0; i < adj[now].size() && stk.top() == now; ++i) {
                    int next = adj[now][i].v;
                    
                    if (dlevel[next] != dlevel[now] + 1 || visit[next])
                        continue;
                    
                    if (adj[now][i].c > adj[now][i].flow) {
                        stk.push(next);
                        prev[next] = {now, i};
                    }
                }
                
                if (stk.top() == now) {
                    stk.pop();
                    visit[now] = 1;
                }
            
            }
            else { // now == sink
                ll f = maxCapacity, bottleneck;
                
                for (int cur = sink; cur != source; cur = abs(prev[cur].first)) {
                    Edge &e = adj[prev[cur].first][prev[cur].second];
                    f = min(f, e.c - e.flow);
                }
                
                for (int cur = sink; cur != source; cur = abs(prev[cur].first)) {
                    
                    Edge &e = adj[prev[cur].first][prev[cur].second];
                    e.flow += f;
                    
                    Edge &e2 = adj[cur][e.rev];
                    e2.flow -= f;
                    
                    if (e.c == e.flow)
                        bottleneck = prev[cur].first;
                }
                
                ret += f;
                
                while(!stk.empty() && stk.top() != bottleneck)
                    stk.pop();
            }
            
        }
        
        return ret;
    }
    
    ll run(int source, int sink) {
        
        ll maxFlow = 0;
        
        while (constructLevel(source, sink)) {
            maxFlow += makeFlow(source, sink);
        }
        
        return maxFlow;
    }
};