ディニッツ法

Dinicの読み方これでいいのかな

init

• 整数\(N\)を与えると、頂点を\(N\)個生成しフローの計算に必要なメモリを確保する
• 計算量は\(Ο(N)\)

Dinic

• コンストラクタ。initを呼ぶ

add

• 頂点\(from\)から\(end\)にかけて容量\(cap\)の有向辺を張る
• 計算量は\(O(1)\)

solve

• 頂点\(s\)を始点、頂点\(t\)を終点としてフローの最大値を求める
• 計算量はinitで与えた頂点の数を\(V\)、addで与えた辺の数を\(E\)として\(Ο(E V^2)\)
• 実際はこれよりも高速に動作する

github

class Dinic{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    struct edge{
        int end;
        long long cap,rev;
        
    };
    
    const long long INF = (1LL<<61);
    int V;
    std::vector<std::vector<edge>> G;
    std::vector<long long> level;
    std::vector<int> iter;
    
    void Dinic_bfs(int s){
        for(int i=0;i<V;i++){
            level[i]=-1;
        }
        std::queue<int> que;
        level[s]=0;
        que.push(s);
        while(!que.empty()){
            int v=que.front();
            que.pop();
            for(unsigned int i=0;i<G[v].size();i++){
                edge &e = G[v][i];
                if(e.cap>0 && level[e.end]<0){
                    level[e.end]=level[v]+1;
                    que.push(e.end);
                }
            }
        }
    }
    
    long long Dinic_dfs(int v,int t,long long f){
        if(v==t)return f;
        for(int &i=iter[v];i<G[v].size();i++){
            edge &e = G[v][i];
            if(e.cap>0 && level[v]<level[e.end]){
                long long d = Dinic_dfs(e.end,t,std::min(f,e.cap));
                if(d>0){
                    e.cap -= d;
                    G[e.end][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    public:
    
    void init(int N){
        V = N;
        G.clear();
        G.resize(V);
        level.resize(V);
        iter.resize(V);
    }
    
    Dinic(int N){
        init(N);
    }
    
    void add(int from,int end,long long cap){
        G[from].push_back((edge){end,cap,(long long)G[end].size()});
        G[end].push_back((edge){from,0,(long long)G[from].size()-1});
    }
    
    long long solve(int s,int t){
        long long flow=0;
        while(1){
            Dinic_bfs(s);
            if(level[t]<0){return flow;}
            for(int i=0;i<V;i++){
                iter[i]=0;
            }
            long long f;
            while((f=Dinic_dfs(s,t,INF))>0){
                flow+=f;
            }
        }
    }
    
};

使用例

---

実行コード

#include <bits/stdc++.h>

class Dinic{/*省略*/};


int main(void){
    
    Dinic dinitz(5);
    dinitz.add(0,1,4);
    dinitz.add(0,2,2);
    dinitz.add(1,2,1);
    dinitz.add(1,3,2);
    dinitz.add(2,3,4);
    dinitz.add(2,4,2);
    dinitz.add(3,4,4);
    
    //このグラフでは頂点0から頂点4へは最大で5つ流れる
    //例えば0->2->4に2つ、0->1->2->3->4に1つ、0->1->3->4に2つなどが考えられる
    long long R = dinitz.solve(0,4);
    std::cout << R << std::endl;
    
    return 0;
}

出力

5

更新履歴

---

日時	内容
2023/06/29	ライセンスのコメントアウトを変更
2021/11/01	githubリンクを追加
2021/11/01	ディニッツ法を追加