#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615"
#include <iostream>
#include "Mylib/Graph/Flow/dinic.cpp"
#include "Mylib/Graph/Flow/max_flow_with_lower_bound.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n, m;
while (std::cin >> n >> m, n) {
auto [u, v] = hl::input_tuple_vector<int, int>(m);
for (auto &x : u) --x;
for (auto &x : v) --x;
auto check =
[&](int lb, int ub) -> bool {
hl::max_flow_with_lower_bound<hl::dinic<int>> flow(n + m + 2);
const int s = n + m, t = s + 1;
for (int i = 0; i < m; ++i) {
flow.add_edge(s, i, 1, 1);
flow.add_edge(i, m + u[i], 0, 1);
flow.add_edge(i, m + v[i], 0, 1);
}
for (int i = 0; i < n; ++i) {
flow.add_edge(m + i, t, lb, ub);
}
return flow.max_flow(s, t).value_or(-1) == m;
};
int lb = 0, ub = n;
for (int l = 0, r = 0; r <= n; ++r) {
while (l <= r and check(l, r)) {
lb = l;
ub = r;
++l;
}
}
std::cout << lb << " " << ub << "\n";
}
return 0;
}
#line 1 "test/aoj/1615/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615"
#include <iostream>
#line 2 "Mylib/Graph/Flow/dinic.cpp"
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace haar_lib {
namespace dinic_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 dinic_impl
template <typename T>
class dinic {
public:
using edge = dinic_impl::edge<T>;
using capacity_type = T;
private:
int size_;
std::vector<std::vector<edge>> g_;
std::vector<int> level_;
bool build_level(int s, int t) {
std::fill(level_.begin(), level_.end(), 0);
level_[s] = 1;
std::queue<int> q;
q.push(s);
while (not q.empty()) {
int cur = q.front();
q.pop();
for (auto &e : g_[cur]) {
if (level_[e.to] == 0 and e.cap > 0) {
level_[e.to] = level_[e.from] + 1;
q.push(e.to);
}
}
}
return level_[t] != 0;
}
void dfs(std::vector<edge *> &path, T &flow, int cur, int t) {
if (cur == t) {
T f = std::numeric_limits<T>::max();
for (auto e : path) {
f = std::min(f, (*e).cap);
}
for (auto e : path) {
(*e).cap -= f;
g_[e->to][e->rev].cap += f;
}
flow += f;
} else {
for (auto &e : g_[cur]) {
if (e.cap > 0 and level_[e.to] > level_[e.from]) {
path.emplace_back(&e);
dfs(path, flow, e.to, t);
path.pop_back();
}
}
}
}
public:
dinic() {}
dinic(int size) : size_(size), g_(size), level_(size) {}
void add_edge(int from, int to, T c) {
assert(0 <= from and from < size_);
assert(0 <= to and to < size_);
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 < size_);
assert(0 <= t and t < size_);
T f = 0;
while (build_level(s, t)) {
T a = 0;
std::vector<edge *> path;
dfs(path, a, s, t);
f += a;
}
return f;
}
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 3 "Mylib/Graph/Flow/max_flow_with_lower_bound.cpp"
#include <optional>
namespace haar_lib {
template <typename Flow>
class max_flow_with_lower_bound {
using edge = typename Flow::edge;
using capacity_type = typename Flow::capacity_type;
int N_, S_, T_;
Flow flow_;
capacity_type min_sum_;
public:
max_flow_with_lower_bound() {}
max_flow_with_lower_bound(int N) : N_(N), S_(N), T_(N + 1), flow_(N + 2), min_sum_(0) {}
void add_edge(int from, int to, capacity_type lb, capacity_type ub) {
assert(0 <= from and from < N_);
assert(0 <= to and to < N_);
assert(0 <= lb and lb <= ub);
flow_.add_edge(from, to, ub - lb);
flow_.add_edge(from, T_, lb);
flow_.add_edge(S_, to, lb);
min_sum_ += lb;
}
std::optional<capacity_type> max_flow(int s, int t) {
assert(0 <= s and s < N_);
assert(0 <= t and t < N_);
auto a = flow_.max_flow(S_, T_);
auto b = flow_.max_flow(s, T_);
auto c = flow_.max_flow(S_, t);
auto d = flow_.max_flow(s, t);
if (a + b == min_sum_ and a + c == min_sum_) return b + d;
return std::nullopt;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#line 7 "Mylib/IO/input_tuple_vector.cpp"
namespace haar_lib {
template <typename T, size_t... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
}
template <typename T, size_t... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
}
template <typename... Args>
auto input_tuple_vector(int N) {
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for (int i = 0; i < N; ++i) {
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
} // namespace haar_lib
#line 7 "test/aoj/1615/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n, m;
while (std::cin >> n >> m, n) {
auto [u, v] = hl::input_tuple_vector<int, int>(m);
for (auto &x : u) --x;
for (auto &x : v) --x;
auto check =
[&](int lb, int ub) -> bool {
hl::max_flow_with_lower_bound<hl::dinic<int>> flow(n + m + 2);
const int s = n + m, t = s + 1;
for (int i = 0; i < m; ++i) {
flow.add_edge(s, i, 1, 1);
flow.add_edge(i, m + u[i], 0, 1);
flow.add_edge(i, m + v[i], 0, 1);
}
for (int i = 0; i < n; ++i) {
flow.add_edge(m + i, t, lb, ub);
}
return flow.max_flow(s, t).value_or(-1) == m;
};
int lb = 0, ub = n;
for (int l = 0, r = 0; r <= n; ++r) {
while (l <= r and check(l, r)) {
lb = l;
ub = r;
++l;
}
}
std::cout << lb << " " << ub << "\n";
}
return 0;
}
test/aoj/1615/main.test.cpp
Dinic algorithm
(Mylib/Graph/Flow/dinic.cpp)