#line 1 "Graph/dinitz.cpp"
/**
* @brief 最大流 (Dinitz 法)
* @author えびちゃん
*/
#include <queue>
#include <vector>
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#include <cstddef>
#include <cstdint>
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
constexpr int8_t operator ""_i8(unsigned long long n) { return n; }
constexpr int16_t operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t operator ""_u8(unsigned long long n) { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }
#line 1 "utility/limits.cpp"
/**
* @brief 型依存の定数
* @author えびちゃん
*/
#include <limits>
#include <utility>
template <typename Tp>
class limits: public std::numeric_limits<Tp> {};
template <typename T1, typename T2>
class limits<std::pair<T1, T2>> {
public:
static constexpr auto min() {
return std::make_pair(limits<T1>::min(), limits<T2>::min());
}
static constexpr auto max() {
return std::make_pair(limits<T1>::max(), limits<T2>::max());
}
};
#line 1 "utility/make/fix_point.cpp"
/**
* @brief ラムダ式の再帰
* @author えびちゃん
*/
#ifndef H_make_fix_point
#define H_make_fix_point
#line 10 "utility/make/fix_point.cpp"
template <typename Fn>
class fix_point: Fn {
public:
explicit constexpr fix_point(Fn&& f) noexcept: Fn(std::forward<Fn>(f)) {}
template <typename... Args>
constexpr decltype(auto) operator ()(Args&&... args) const {
return Fn::operator ()(*this, std::forward<Args>(args)...);
}
};
template <typename Fn>
static inline constexpr decltype(auto) make_fix_point(Fn&& f) noexcept {
return fix_point<Fn>{std::forward<Fn>(f)};
}
#endif /* !defined(H_make_fix_point) */
#line 15 "Graph/dinitz.cpp"
struct dinitz_tag {} dinitz;
template <typename AdjacencyList>
auto max_flow(AdjacencyList& g, size_t s, size_t t,
typename AdjacencyList::weight_type fl, dinitz_tag) {
using size_type = typename AdjacencyList::size_type;
using weight_type = typename AdjacencyList::weight_type;
size_type n = g.size();
std::vector<size_type> level(n), iter(n);
auto bfs = [&](size_type s) -> void {
level.assign(n, -1_zu);
std::queue<size_type> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
size_type v = q.front();
q.pop();
for (auto const& e: g[v]) {
if (e.capacity() > weight_type(0) && level[e.target()] == -1_zu) {
level[e.target()] = level[e.source()] + 1;
q.push(e.target());
}
}
}
};
auto dfs = make_fix_point([&](auto dfs_, size_type v, weight_type f) -> weight_type {
if (v == t) return f;
for (size_type& i = iter[v]; i < g[v].size(); ++i) {
auto& e = g[v][i];
if (e.capacity() > weight_type(0) && level[v] < level[e.target()]) {
weight_type f0 = dfs_(e.target(), std::min(f, e.capacity()));
if (f0 > weight_type(0)) {
e.capacity() -= f0;
g[e.target()][e.reversed()].capacity() += f0;
return f0;
}
}
}
return weight_type(0);
});
weight_type res{0};
while (true) {
bfs(s);
if (level[t] == -1_zu) return res;
iter.assign(n, 0);
weight_type f;
while ((f = dfs(s, fl)) > weight_type(0)) {
res += f;
fl -= f;
if (fl == weight_type(0)) return res;
}
}
}
template <typename AdjacencyList>
auto max_flow(AdjacencyList& g, size_t s, size_t t, dinitz_tag) {
auto fl = limits<typename AdjacencyList::weight_type>::max();
return max_flow(g, s, t, fl, dinitz);
}
最大流 (Dinitz 法) (Graph/dinitz.cpp)