Dinic法を書いてみた(まだ使えない)

とあるツイートが流れてきたので勉強してみた

参考になった記事

ACM-ICPC Dinic's Algorithm

Dinic法-Algoogle

流れ

level graph(Sからの最短距離)をつくる(BFS)

このとき必ず、まだflowを流せる辺(許容範囲が0より大きい辺)を選ぶ

2.level graphでのpathをすべて探索(DFS)

      あと2           あと3
    ========>     ========> 
[1]           [2]           [3]
    <--------     <--------
      あと0           あと0

という経路(===>)をとった時
このpathに流せるflowは2

2を引き、逆向きの辺に2を足す

      あと0           あと1
    ========>     ========> 
[1]           [2]           [3]
    <--------     <--------
      あと2           あと2

3.level graphがTに到達できなくなるまで繰り返す

実装してみる

上の参考にしたページとほぼ同じ(参考にしたから当たり前)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Dinic
{
    struct edge
    {
        int to;
        int cap;
        int rev;
    };

    vector<vector<edge>> G;
    int N;
    vector<int> level;
    vector<int> itr;

    Dinic(int n) : N(n)
    {
        G.assign(N,vector<edge>());
    }

    void add_edge(int from ,int to,int cap)
    {
        G[from].push_back({to,cap,(int)G[to].size()});
        G[to].push_back({from,0,(int)G[from].size() - 1});
    }

    //tに到達できない...falseを返す
    bool g_level(int s,int t)
    {
        level.assign(N,-1);
        queue<int> que;
        que.push(s);
        level[s] = 0;
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            for(edge& e : G[v])
            {
                if(e.cap > 0 && level[e.to] == -1)
                {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    //辿った経路での最小の容量を返す
    int dfs(int v,int t,int f)
    {
        if(v == t) return f;

        for(int& i = itr[v];i < G[v].size();i++)
        {
            edge& e = G[v][i];
            if(e.cap > 0 && level[e.to] > level[v])
            {
                int mi_f = dfs(e.to,t,min(f,e.cap));
                if(mi_f > 0)
                {
                    e.cap -= mi_f;
                    G[e.to][e.rev].cap += mi_f;
                    return mi_f;
                }
            }
        }
        return 0;
    }

    int max_flow(int s,int t)
    {
        int result = 0;
        int flow;
        while(g_level(s,t))
        {
            itr.assign(N,0);
            while((flow = dfs(s,t,1e9)) > 0) result += flow;
        }
        return result;
    }
};


/*
checked:
   http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2722839#1
*/

まだ書いただけなので実際にどんな問題に使えるかを勉強しなきゃ