FordFulkerson
(graph/fordfulkerson.hpp)

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

説明

最大流を Ford-Fulkerson 法で求める。うしライブラリを改変して高速に書けるようにした。

コンストラクタ

FordFulkerson<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 へ流せる限り流し、流せた量を返す。計算量は、流量を F, 辺数を M として O(FM)

実装例

int main(){
	int n, m; cin >> n >> m;
	lib::FordFulkerson<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 <typename fa> struct FordFulkerson {
    struct edge {
        int to;
        fa cap;
        int rev;
        bool isrev;
    };

    const fa INF;
    vector<vector<edge>> g;
    vector<int> used;
    int ts;

    explicit FordFulkerson(int v)
        : INF(numeric_limits<fa>::max()), g(v), used(v, -1), ts(0) {}

    void add_edge(int from, int to, fa cap) {
        g[from].push_back((edge){to, cap, (int)g[to].size(), false});
        g[to].push_back((edge){from, 0, (int)g[from].size() - 1, true});
    }
    fa dfs(int v, int t, fa flow) {
        if (v == t) return flow;
        used[v] = ts;
        for (auto &e : g[v]) {
            if (e.cap > 0 && used[e.to] != ts) {
                fa d = dfs(e.to, t, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    fa flow(int s, int t) {
        fa ret = 0;
        for (fa f; (f = dfs(s, t, INF)) > 0; ts++) ret += f;
        ts++;
        return ret;
    }
};

}  // 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/fordfulkerson.hpp"

namespace lib {
using namespace std;

template <typename fa> struct FordFulkerson {
    struct edge {
        int to;
        fa cap;
        int rev;
        bool isrev;
    };

    const fa INF;
    vector<vector<edge>> g;
    vector<int> used;
    int ts;

    explicit FordFulkerson(int v)
        : INF(numeric_limits<fa>::max()), g(v), used(v, -1), ts(0) {}

    void add_edge(int from, int to, fa cap) {
        g[from].push_back((edge){to, cap, (int)g[to].size(), false});
        g[to].push_back((edge){from, 0, (int)g[from].size() - 1, true});
    }
    fa dfs(int v, int t, fa flow) {
        if (v == t) return flow;
        used[v] = ts;
        for (auto &e : g[v]) {
            if (e.cap > 0 && used[e.to] != ts) {
                fa d = dfs(e.to, t, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    fa flow(int s, int t) {
        fa ret = 0;
        for (fa f; (f = dfs(s, t, INF)) > 0; ts++) ret += f;
        ts++;
        return ret;
    }
};

}  // namespace lib

Back to top page