Dinic Algorithm (1)

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

// Dinic to find max-flow/min-cut
// Usage: 
//      Dinic dinic; 
//      dinic.init(n); 
//      dinic.addEdge(...); 
//      maxFlow = dinic.run(source, sink);
struct Dinic {
    int n;
    vector< vector<ll> > capa;
    vector< vector<ll> > flow;
    vector< vector<int> > adj;
    vector<int> dlevel;
    vector<int> prev;
    vector<int> visit;
    
    int maxCapacity;
    
    Dinic(){
        maxCapacity = 1e9;
    }
    
    void init(int n_) {
        n = n_;
        
        capa.resize(n+1);       
        flow.resize(n+1);
        adj.resize(n+1);
        dlevel.resize(n+1);
        prev.resize(n+1, 0);
        visit.resize(n+1);
        
        for (int i = 0; i <= n; ++i) {
            capa[i].resize(n+1);
            flow[i].resize(n+1);    
            fill(capa[i].begin(), capa[i].begin()+n+1, 0);      
            fill(flow[i].begin(), flow[i].begin()+n+1, 0);  
            adj[i].clear();
        }
        
        fill(dlevel.begin(), dlevel.begin()+n+1, 0);    
        fill(prev.begin(), prev.begin()+n+1, 0);    
        fill(visit.begin(), visit.begin()+n+1, 0);  
    }
    
    void addEdge(int u, int v, int w) {
        capa[u][v] += w;
        capa[v][u] += w;
        flow[v][u] += w;
    }
    
    void prepareAdj() {
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j)
                if (i != j && capa[i][j] > 0)
                    adj[i].push_back(j);
    }
    
    bool constructLevel(int source, int sink) {
        fill(dlevel.begin(), dlevel.begin()+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];
                if (dlevel[next] >= 0)
                    continue;
                
                if (capa[vertex][next] > flow[vertex][next]) {
                    que.push(next);
                    dlevel[next] = dlevel[vertex] + 1;
                }
                
            }
        }
        
        return dlevel[sink] >= 0;
    }
    
    ll makeFlow(int source, int sink) {
        
        ll ret = 0;
        
        fill(visit.begin(), visit.begin()+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];
                    
                    if (dlevel[next] != dlevel[now] + 1 || visit[next])
                        continue;
                    
                    if (capa[now][next] > flow[now][next]) {
                        stk.push(next);
                        prev[next] = now;
                    }
                }
                
                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])) {
                    f = min(f, capa[prev[cur]][cur] - flow[prev[cur]][cur]);
                }
                
                for (int cur = sink; cur != source; cur = abs(prev[cur])) {

                    flow[prev[cur]][cur] += f;
                    flow[cur][prev[cur]] -= f;
                    
                    if (capa[prev[cur]][cur] == flow[prev[cur]][cur])
                        bottleneck = prev[cur];
                }
                
                ret += f;
                
                while(!stk.empty() && stk.top() != bottleneck)
                    stk.pop();
            }
            
        }
        
//      cout << "ret: " << ret << endl;
        return ret;
    }
    
    ll run(int source, int sink) {
        
        prepareAdj();
        
        ll maxFlow = 0;
        
        while (constructLevel(source, sink)) {
            maxFlow += makeFlow(source, sink);
        }
        
        return maxFlow;
    }
};