template<typename T> class Dinic {
private:
    int V;
    vector<int> level,iter;
    void bfs(int s) {
        fill(level.begin(),level.end(),-1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for(auto& e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    T dfs(int v,int t,T f) {
        if(v==t){
            return f;
        }
        for(int& i = iter[v]; i < (int)G[v].size(); i++){
            edge& e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                T d = dfs(e.to,t,min(f,e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
 
public:
    struct edge{
        int to, rev;
        T cap;
    };
    vector<vector<edge> > G;
 
    Dinic(const int node_size) : V(node_size), level(V), iter(V), G(V){}
    //辺を張る
    void add_edge(int from,int to,T cap) {
        G[from].push_back((edge){to, (int)G[to].size(), cap});
        G[to].push_back((edge){from, (int)G[from].size()-1, (T)0});
    }
    //最大流を計算
    T solve(int s,int t) {
        T flow = 0;
        for(;;){
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(),iter.end(),0);
            T f;
            while((f=dfs(s,t,numeric_limits<T>::max())) > 0){
                flow += f;
            }
        }
    }
};

コード(容量スケーリング版)

template<typename T> class Dinic {
public:
    static_assert(std::is_integral<T>::value, "Integral required.");
    struct edge{
        int to;
        T cap;
        int rev;
    };
private:
    const int V;
    T max_cap;
    vector<int> level, iter, que;
    static unsigned long long floor2(unsigned long long v){
        v = v | (v >> 1), v = v | (v >> 2);
        v = v | (v >> 4), v = v | (v >> 8);
        v = v | (v >> 16), v = v | (v >> 32);
        return v - (v >> 1);
    }
    void bfs(const int s, const T base) {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        int qh = 0, qt = 0;
        for(que[qt++] = s; qh < qt;){
            int v = que[qh++];
            for(edge& e : G[v]){
                if(level[e.to] < 0 && e.cap >= base){
                    level[e.to] = level[v] + 1;
                    que[qt++] = e.to;
                }
            }
        }
    }
    T dfs(const int v, const int t, const T base, const T f) {
        if(v == t) return f;
        T sum = 0;
        for(int& i = iter[v]; i < (int)G[v].size(); i++){
            edge& e = G[v][i];
            if(e.cap >= base && level[v] < level[e.to]){
                T d = dfs(e.to, t, base, min(f - sum, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    sum += d;
                    if(f - sum < base) break;
                }
            }
        }
        return sum;
    }
 
public:
    vector<vector<edge> > G;
 
    Dinic(const int node_size) : V(node_size), max_cap(0), level(V), iter(V), que(V), G(V){}
    //辺を張る
    void add_edge(const int from, const int to, const T cap) {
        G[from].push_back((edge){to, cap, (int)G[to].size()});
        G[to].push_back((edge){from, (T)0, (int)G[from].size()-1});
        max_cap = max(max_cap, cap);
    }
    //最大流を計算(max_cap は辺の容量の上限)
    T solve(const int s, const int t){
        T flow = 0;
        for(T base = floor2(max_cap); base >= 1;){
            bfs(s, base);
            if(level[t] < 0){
                base >>= 1;
                continue;
            }
            fill(iter.begin(), iter.end(), 0);
            flow += dfs(s, t, base, numeric_limits<T>::max());
        }
        return flow;
    }
};