max flow
(graph/mf_graph.hpp)

• View this file on GitHub
• Last update: 2023-05-17 22:41:14+09:00
• Include: #include "graph/mf_graph.hpp"

説明

最大流を Dinic 法で求める。ACLを改変して比較的高速に書けるようにした。

コンストラクタ

mf_graph<Cap> graph(int n)

n 頂点 0 辺のグラフを作る。Cap は容量の型。

add_edge(int from, int to, Cap cap)

from→to へ最大容量 cap、流量 0 の辺を追加する。

flow(int s, int t)

頂点 s から t へ流せる限り流し、流せた量を返す。 計算量は、m を辺数として $O(min(n^{2/3}m, m^{3/2}))$ (辺容量がすべて 1)、 $O(n^2m)$ (一般)。

flow(int s, int t, Cap flow_limit) で限界もつくれる。

注意

以下のコメントアウトされている。必要なときに取り出す。

get_edge / edges

mf_graph<Cap>::edge graph.get_edge(int i);
vector<mf_graph<Cap>::edge> graph.edges();

辺の状態を返す。

change_edge

void graph.change_edge(int i, Cap new_cap, Cap new_flow);

その辺のみの容量と流量を変えて、他は変更しない。使い所よくわからず。

min_cut

vector<bool> graph.min_cut(int s)

残余グラフに対して, 頂点 s から到達可能かどうかを返す。とくに flow(s,t) してから呼ぶと最小カットに対応する。

実装例

int main(){
	int n, m; cin >> n >> m;
	lib::mf_graph<int> mf(n);
	for(int i=0;i<m;i++){
		int u,v,c;cin>>u>>v>>c;
		mf.add_edge(u,v,c);
	}
	cout<<mf.flow(0,n-1)<<endl;
}

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/graph/Maximum_Flow.test.cpp

Code

#pragma once
#include "../template/template.hpp"

namespace lib {
using namespace std;

template <class Cap> struct mf_graph {
    struct edge {
        int from, to;
        Cap cap, flow;
    };

    struct nedge {
        int to, rev;
        Cap cap;
    };

    int nn;
    vector<pair<int, int>> pos;
    vector<vector<nedge>> g;

    mf_graph() : nn(0) {}
    explicit mf_graph(int n) : nn(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        int m = pos.size();
        pos.push_back({from, int(g[from].size())});
        int frid = int(g[from].size());
        int toid = int(g[to].size());
        if (from == to) toid++;
        g[from].push_back(nedge{to, toid, cap});
        g[to].push_back(nedge{from, frid, 0});
        return m;
    }

    Cap flow(int s, int t) {
        return flow(s, t, numeric_limits<Cap>::max());
    }

    Cap flow(int s, int t, Cap flow_limit) {
        vector<int> lv(nn), iter(nn);
        queue<int> q;

        auto bfs = [&]() {
            fill(all(lv), -1);
            lv[s] = 0;
            queue<int>().swap(q);
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || lv[e.to] >= 0) continue;
                    lv[e.to] = lv[v] + 1;
                    if (e.to == t) return;
                    q.push(e.to);
                }
            }
        };

        auto dfs = [&](auto self, int v, Cap up) {
            if (v == s) return up;
            Cap res = 0;
            int lvvv = lv[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                nedge& e = g[v][i];
                if (lvvv <= lv[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d = self(self, e.to, min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            lv[v] = nn;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (lv[t] == -1) break;
            fill(all(iter), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    /*

if you want other functions, take from here
NOT VERIFIED.

edge get_edge(int i) {
    int m = int(pos.size());
    auto _e = g[pos[i].first][pos[i].second];
    auto _re = g[_e.to][_e.rev];
    return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}

vector<edge> edges() {
    int m = int(pos.size());
    vector<edge> result;
    for (int i = 0; i < m; i++) {
        result.push_back(get_edge(i));
    }
    return result;
}

void change_edge(int i, Cap new_cap, Cap new_flow) {
    int m = int(pos.size());
    auto& _e = g[pos[i].first][pos[i].second];
    auto& _re = g[_e.to][_e.rev];
    _e.cap = new_cap - new_flow;
    _re.cap = new_flow;
}

std::vector<bool> min_cut(int s) {
    vector<bool> visited(_n);
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        visited[p] = true;
        for (auto e : g[p]) {
            if (e.cap && !visited[e.to]) {
                visited[e.to] = true;
                q.push(e.to);
            }
        }
    }
    return visited;
}

    */
};

}  // namespace lib

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 3 "graph/mf_graph.hpp"

namespace lib {
using namespace std;

template <class Cap> struct mf_graph {
    struct edge {
        int from, to;
        Cap cap, flow;
    };

    struct nedge {
        int to, rev;
        Cap cap;
    };

    int nn;
    vector<pair<int, int>> pos;
    vector<vector<nedge>> g;

    mf_graph() : nn(0) {}
    explicit mf_graph(int n) : nn(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        int m = pos.size();
        pos.push_back({from, int(g[from].size())});
        int frid = int(g[from].size());
        int toid = int(g[to].size());
        if (from == to) toid++;
        g[from].push_back(nedge{to, toid, cap});
        g[to].push_back(nedge{from, frid, 0});
        return m;
    }

    Cap flow(int s, int t) {
        return flow(s, t, numeric_limits<Cap>::max());
    }

    Cap flow(int s, int t, Cap flow_limit) {
        vector<int> lv(nn), iter(nn);
        queue<int> q;

        auto bfs = [&]() {
            fill(all(lv), -1);
            lv[s] = 0;
            queue<int>().swap(q);
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || lv[e.to] >= 0) continue;
                    lv[e.to] = lv[v] + 1;
                    if (e.to == t) return;
                    q.push(e.to);
                }
            }
        };

        auto dfs = [&](auto self, int v, Cap up) {
            if (v == s) return up;
            Cap res = 0;
            int lvvv = lv[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                nedge& e = g[v][i];
                if (lvvv <= lv[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d = self(self, e.to, min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            lv[v] = nn;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (lv[t] == -1) break;
            fill(all(iter), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    /*

if you want other functions, take from here
NOT VERIFIED.

edge get_edge(int i) {
    int m = int(pos.size());
    auto _e = g[pos[i].first][pos[i].second];
    auto _re = g[_e.to][_e.rev];
    return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}

vector<edge> edges() {
    int m = int(pos.size());
    vector<edge> result;
    for (int i = 0; i < m; i++) {
        result.push_back(get_edge(i));
    }
    return result;
}

void change_edge(int i, Cap new_cap, Cap new_flow) {
    int m = int(pos.size());
    auto& _e = g[pos[i].first][pos[i].second];
    auto& _re = g[_e.to][_e.rev];
    _e.cap = new_cap - new_flow;
    _re.cap = new_flow;
}

std::vector<bool> min_cut(int s) {
    vector<bool> visited(_n);
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        visited[p] = true;
        for (auto e : g[p]) {
            if (e.cap && !visited[e.to]) {
                visited[e.to] = true;
                q.push(e.to);
            }
        }
    }
    return visited;
}

    */
};

}  // namespace lib

Back to top page