graph/graph_018_dinic.cpp

• View this file on GitHub
• Last update: 2019-11-22 21:50:52+09:00

Code

// Dinic を信じろ

template <typename CapTp=int, typename CostTp=int>
struct Edge {
    int to, rev;
    CapTp cap; CostTp cost;
    bool is_rev;
    Edge(int t, bool f, int r, CapTp ca, CostTp co=0)
        : to(t), rev(r), cap(ca), cost(co), is_rev(f) {}
};

template<typename CapTp=int>
struct Dinic {
    using Graph = vector< vector< Edge<CapTp> > >;
    Graph G;
    vector<int> level, iter;
    const CapTp IA;
    vector< pair<int, int> > r_edges;
    Dinic(int N, CapTp IA_=1<<29) : IA(IA_) {
        G.resize(N);
        level.resize(N);
        iter.resize(N);
    }
    void add_edge(int from, int to, CapTp cap) {
        G[from].emplace_back(to, false, G[to].size(), cap);
        G[to].emplace_back(from, true, G[from].size() - 1, 0);
        r_edges.emplace_back(to, G[to].size() - 1);
    }
    CapTp get_flowed_cap(size_t k) {
        if(r_edges.size() <= k) return -1;
        int v, i; tie(v, i) = r_edges[k];
        return G[v][i].cap;
    }
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> que; que.push(s);
        level[s] = 0;
        while(!que.empty()) {
            int temp = que.front(); que.pop();
            for(size_t i=0; i<G[temp].size(); i++) {
                auto &e = G[temp][i];
                if(e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[temp] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    CapTp dfs(int v, int t, CapTp f) {
        if(v == t) return f;
        for(int &i = iter[v]; i<(int)G[v].size(); i++) {
            auto &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]) {
                CapTp 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;
    }
    CapTp max_flow(int s, int t) {
        CapTp flow = 0.0, f;
        while(1) {
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            while( (f = dfs(s, t, IA)) > 0 ) flow += f;
        }
    }
};

// 最小流量制約付きフロー
// u から v に最小 lb, 最大 ub 流す
template<typename flow_type>
struct Dinic_lr {
    Dinic<flow_type> fl;
    int S, T;
    flow_type sum_lb;

    Dinic_lr() {}
    Dinic_lr(int N) : fl(N+2, 0), S(N), T(N+1), sum_lb(0) {}

    void add_edge(int u, int v, flow_type lb, flow_type ub) {
        assert(0 <= lb && lb <= ub);
        if(u == v || ub == 0) return;
        fl.add_edge(u, v, ub - lb);
        fl.add_edge(S, v, lb);
        fl.add_edge(u, T, lb);
        sum_lb += lb;
    }

    flow_type max_flow(int s, int t) {
        flow_type a = fl.max_flow(S, T);
        flow_type b = fl.max_flow(s, T);
        flow_type c = fl.max_flow(S, t);
        flow_type d = fl.max_flow(s, t);
        return (a + c == sum_lb && a + b == sum_lb) ? b + d : -1;
    }
};

#line 1 "graph/graph_018_dinic.cpp"
// Dinic を信じろ

template <typename CapTp=int, typename CostTp=int>
struct Edge {
    int to, rev;
    CapTp cap; CostTp cost;
    bool is_rev;
    Edge(int t, bool f, int r, CapTp ca, CostTp co=0)
        : to(t), rev(r), cap(ca), cost(co), is_rev(f) {}
};

template<typename CapTp=int>
struct Dinic {
    using Graph = vector< vector< Edge<CapTp> > >;
    Graph G;
    vector<int> level, iter;
    const CapTp IA;
    vector< pair<int, int> > r_edges;
    Dinic(int N, CapTp IA_=1<<29) : IA(IA_) {
        G.resize(N);
        level.resize(N);
        iter.resize(N);
    }
    void add_edge(int from, int to, CapTp cap) {
        G[from].emplace_back(to, false, G[to].size(), cap);
        G[to].emplace_back(from, true, G[from].size() - 1, 0);
        r_edges.emplace_back(to, G[to].size() - 1);
    }
    CapTp get_flowed_cap(size_t k) {
        if(r_edges.size() <= k) return -1;
        int v, i; tie(v, i) = r_edges[k];
        return G[v][i].cap;
    }
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> que; que.push(s);
        level[s] = 0;
        while(!que.empty()) {
            int temp = que.front(); que.pop();
            for(size_t i=0; i<G[temp].size(); i++) {
                auto &e = G[temp][i];
                if(e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[temp] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    CapTp dfs(int v, int t, CapTp f) {
        if(v == t) return f;
        for(int &i = iter[v]; i<(int)G[v].size(); i++) {
            auto &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]) {
                CapTp 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;
    }
    CapTp max_flow(int s, int t) {
        CapTp flow = 0.0, f;
        while(1) {
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            while( (f = dfs(s, t, IA)) > 0 ) flow += f;
        }
    }
};

// 最小流量制約付きフロー
// u から v に最小 lb, 最大 ub 流す
template<typename flow_type>
struct Dinic_lr {
    Dinic<flow_type> fl;
    int S, T;
    flow_type sum_lb;

    Dinic_lr() {}
    Dinic_lr(int N) : fl(N+2, 0), S(N), T(N+1), sum_lb(0) {}

    void add_edge(int u, int v, flow_type lb, flow_type ub) {
        assert(0 <= lb && lb <= ub);
        if(u == v || ub == 0) return;
        fl.add_edge(u, v, ub - lb);
        fl.add_edge(S, v, lb);
        fl.add_edge(u, T, lb);
        sum_lb += lb;
    }

    flow_type max_flow(int s, int t) {
        flow_type a = fl.max_flow(S, T);
        flow_type b = fl.max_flow(s, T);
        flow_type c = fl.max_flow(S, t);
        flow_type d = fl.max_flow(s, t);
        return (a + c == sum_lb && a + b == sum_lb) ? b + d : -1;
    }
};

Back to top page