graph/fordfulkerson.hpp

• View this file on GitHub
• Last update: 2025-08-08 21:59:02+09:00
• Include: #include "graph/fordfulkerson.hpp"

Depends on

• graph/flowtemplate.hpp

Code

#pragma once
#include <bits/stdc++.h>
using namespace std;
#include "flowtemplate"

template <class T>
T fordfullkerson(flowgraph<T>& g, int s=0, int t=-1) {
    if (t == -1) t = g.size()-1;
    T re = T{};
    auto f = [&](auto&& self, int from, int to, T lim, vector<char>& used) -> T {
        if (from == to) return lim;
        used[from] = true;
        for (int i=0; i<(int)g[from].size(); i++) {
            flowedge<T>& _e = g[from][i];
            if (!used[_e.to] && 0<_e.cap) {
                T r = self(self, _e.to, to, min(lim, _e.cap), used);
                if (T{} < r) {
                    _e.cap -= r;
                    g[_e.to][_e.rev] += r;
                    return r;
                }
            }
        }
        return T{};
    };
    while (true) {
        vector<char> used(g.size());
        int flow = f(f, s, t, numeric_limits<T>::max(), used);
        if (flow == T{}) break;
        re += flow;
    }
    return re;
}

#line 2 "graph/fordfulkerson.hpp"
#include <bits/stdc++.h>
using namespace std;
#line 3 "graph/flowtemplate.hpp"
using namespace std;

template <class T>
struct flowedge {
    int to;
    T cap;
    int rev;
};

template <class T>
using flowedges = vector<flowedge<T>>;

template <class T>
struct flowgraph {
    vector<flowedges<T>> data;
    flowgraph() = default;
    flowgraph(int n) : data(n) {}
    void add_edge(int from, int to, T cap = numeric_limits<T>::max()) {
        if (id == -1) id = _edges.size();
        data[from].push_back(flowedge<T>{to, cap, data[to].size()});
        data[to].push_back(flowedge<T>{from, T{}, data[from].size()-1});
    }
    int size() {
        return data.size();
    }
    flowedges<T> operator[](int k) {
        return data[k];
    }
};
#line 5 "graph/fordfulkerson.hpp"

template <class T>
T fordfullkerson(flowgraph<T>& g, int s=0, int t=-1) {
    if (t == -1) t = g.size()-1;
    T re = T{};
    auto f = [&](auto&& self, int from, int to, T lim, vector<char>& used) -> T {
        if (from == to) return lim;
        used[from] = true;
        for (int i=0; i<(int)g[from].size(); i++) {
            flowedge<T>& _e = g[from][i];
            if (!used[_e.to] && 0<_e.cap) {
                T r = self(self, _e.to, to, min(lim, _e.cap), used);
                if (T{} < r) {
                    _e.cap -= r;
                    g[_e.to][_e.rev] += r;
                    return r;
                }
            }
        }
        return T{};
    };
    while (true) {
        vector<char> used(g.size());
        int flow = f(f, s, t, numeric_limits<T>::max(), used);
        if (flow == T{}) break;
        re += flow;
    }
    return re;
}

Back to top page