#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"
#include <climits>
#include <iostream>
#include "Mylib/Graph/Flow/push_relabel.cpp"
#include "Mylib/IO/input_tuples.cpp"
namespace hl = haar_lib;
int main() {
int V, E;
std::cin >> V >> E;
hl::push_relabel<int> f(V);
for (auto [s, t, c] : hl::input_tuples<int, int, int>(E)) {
f.add_edge(s, t, c);
}
auto ans = f.max_flow(0, V - 1);
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/aoj/GRL_6_A/main.push_relabel.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"
#include <climits>
#include <iostream>
#line 2 "Mylib/Graph/Flow/push_relabel.cpp"
#include <cassert>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace haar_lib {
namespace push_relabel_impl {
template <typename T>
struct edge {
int from, to, rev;
T cap;
bool is_rev;
edge(int from, int to, int rev, T cap, bool is_rev) : from(from), to(to), rev(rev), cap(cap), is_rev(is_rev) {}
};
} // namespace push_relabel_impl
template <typename T>
class push_relabel {
public:
using edge = push_relabel_impl::edge<T>;
using capacity_type = T;
private:
int N_;
std::vector<std::vector<edge>> g_;
std::vector<T> excess_;
std::vector<int> height_;
std::queue<int> next_active_vertex_;
constexpr static T inf = std::numeric_limits<T>::max();
void init(int s, int t) {
excess_[s] = inf;
for (auto &e : g_[s]) {
push(e, s, t);
}
{
for (int i = 0; i < N_; ++i) {
height_[i] = N_;
}
std::queue<int> q;
std::vector<bool> check(N_);
q.push(t);
height_[t] = 0;
while (not q.empty()) {
const int i = q.front();
q.pop();
if (check[i]) continue;
check[i] = true;
for (auto &e : g_[i]) {
if (not e.is_rev) continue;
if (height_[e.from] + 1 < height_[e.to]) {
height_[e.to] = height_[e.from] + 1;
q.push(e.to);
}
}
}
height_[s] = N_;
}
}
bool is_pushable(const edge &e) {
if (excess_[e.from] == 0) return false;
if (height_[e.from] != height_[e.to] + 1) return false;
if (e.cap == 0) return false;
return true;
}
void push(edge &e, int, int) {
auto &r = g_[e.to][e.rev];
T flow = std::min(e.cap, excess_[e.from]);
e.cap -= flow;
r.cap += flow;
excess_[e.from] -= flow;
excess_[e.to] += flow;
if (excess_[e.to] == flow) next_active_vertex_.push(e.to);
}
void relabel(int i, int, int) {
int a = std::numeric_limits<int>::max() / 2;
for (auto &e : g_[i]) {
if (e.cap > 0) a = std::min(a, height_[e.to]);
}
height_[i] = a + 1;
}
public:
push_relabel() {}
push_relabel(int N) : N_(N), g_(N), excess_(N), height_(N) {}
void add_edge(int from, int to, T c) {
assert(0 <= from and from < N_);
assert(0 <= to and to < N_);
g_[from].emplace_back(from, to, (int) g_[to].size(), c, false);
g_[to].emplace_back(to, from, (int) g_[from].size() - 1, 0, true);
}
T max_flow(int s, int t) {
assert(0 <= s and s < N_);
assert(0 <= t and t < N_);
init(s, t);
while (true) {
int index = -1;
while (not next_active_vertex_.empty()) {
int i = next_active_vertex_.front();
if (i != s and i != t and excess_[i] > 0) {
index = i;
break;
}
next_active_vertex_.pop();
}
if (index == -1) break;
bool ok = false;
for (auto &e : g_[index]) {
if (is_pushable(e)) {
push(e, s, t);
ok = true;
break;
}
}
if (not ok) {
relabel(index, s, t);
}
}
return excess_[t];
}
std::vector<edge> edges() const {
std::vector<edge> ret;
for (auto &v : g_) ret.insert(ret.end(), v.begin(), v.end());
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 7 "test/aoj/GRL_6_A/main.push_relabel.test.cpp"
namespace hl = haar_lib;
int main() {
int V, E;
std::cin >> V >> E;
hl::push_relabel<int> f(V);
for (auto [s, t, c] : hl::input_tuples<int, int, int>(E)) {
f.add_edge(s, t, c);
}
auto ans = f.max_flow(0, V - 1);
std::cout << ans << std::endl;
return 0;
}
test/aoj/GRL_6_A/main.push_relabel.test.cpp
Input tuple
(Mylib/IO/input_tuple.cpp)