incremental_msf.hpp¶
只增加边时维护最小生成森林，并报告新边替换了哪条更重的树边。
Complexity: Time: Amortized O(log n) per inserted edge. Space: O(n), independent of the number of rejected edges.
AC 记录：incremental_minimum_spanning_forest。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Amortized O(log n) per inserted edge.
/// Space: O(n), independent of the number of rejected edges.
#include "noya/link_cut_tree.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
namespace incremental_msf_detail {
template <class Weight> struct maximum_edge_monoid {
using value_type = std::pair<Weight, int>;
static value_type unit() {
return {std::numeric_limits<Weight>::lowest(), -1};
}
static value_type op(const value_type &l, const value_type &r) {
return std::max(l, r);
}
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest under edge insertions.
/// Represent every selected edge by an extra Link-Cut Tree vertex carrying
/// (weight,id), while original vertices carry minus infinity. A cycle-forming
/// insertion exposes its endpoint path: the heaviest selected edge is replaced
/// exactly when it is heavier. Removed edge vertices are reused, so at most
/// n-1 extra nodes are needed even for an arbitrarily long insertion stream.
template <class Weight> class incremental_minimum_spanning_forest {
using monoid = incremental_msf_detail::maximum_edge_monoid<Weight>;
using value_type = typename monoid::value_type;
public:
explicit incremental_minimum_spanning_forest(int n) : n_(n) {
assert(n >= 0);
tr_.build(std::vector<value_type>(
std::size_t(n) + std::size_t(std::max(0, n - 1)), monoid::unit()));
end.resize(std::size_t(std::max(0, n - 1)));
}
/// @brief Insert an edge with a globally unique weight and ID. Return -1
/// when it increases the forest size; otherwise return the removed edge ID,
/// which equals id itself when the new edge is rejected.
int add_edge(int a, int b, Weight w, int id) {
assert(0 <= a && a < n_);
assert(0 <= b && b < n_);
if (!tr_.connected(a, b)) {
assert(us < std::max(0, n_ - 1));
install(us++, a, b, w, id);
return -1;
}
auto [mxw, mxi] = tr_.path_product(a, b);
if (w > mxw) {
return id;
}
int sl = its[mxi];
auto [oa, ob] = end[sl];
int ev = n_ + sl;
bool ca = tr_.cut(ev, oa);
bool cb = tr_.cut(ev, ob);
assert(ca && cb);
install(sl, a, b, w, id);
return mxi;
}
private:
int n_ = 0;
int us = 0;
link_cut_tree<monoid> tr_;
std::vector<std::pair<int, int>> end;
std::vector<int> its;
void install(int sl, int a, int b, Weight w, int id) {
assert(id >= 0);
if (int(its.size()) <= id) {
its.resize(id + 1, -1);
}
its[id] = sl;
end[sl] = {a, b};
int ev = n_ + sl;
tr_.set(ev, {w, id});
bool la = tr_.link(a, ev);
bool lb = tr_.link(b, ev);
assert(la && lb);
}
};
} // namespace noya
#ifndef NOYA_INCREMENTAL_MSF_HPP
#define NOYA_INCREMENTAL_MSF_HPP 1
/// @complexity Time: Amortized O(log n) per inserted edge.
/// Space: O(n), independent of the number of rejected edges.
#include "noya/link_cut_tree.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
namespace incremental_msf_detail {
template <class Weight> struct maximum_edge_monoid {
using value_type = std::pair<Weight, int>;
static value_type unit() {
return {std::numeric_limits<Weight>::lowest(), -1};
}
static value_type op(const value_type &l, const value_type &r) {
return std::max(l, r);
}
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest under edge insertions.
/// Represent every selected edge by an extra Link-Cut Tree vertex carrying
/// (weight,id), while original vertices carry minus infinity. A cycle-forming
/// insertion exposes its endpoint path: the heaviest selected edge is replaced
/// exactly when it is heavier. Removed edge vertices are reused, so at most
/// n-1 extra nodes are needed even for an arbitrarily long insertion stream.
template <class Weight> class incremental_minimum_spanning_forest {
using monoid = incremental_msf_detail::maximum_edge_monoid<Weight>;
using value_type = typename monoid::value_type;
public:
explicit incremental_minimum_spanning_forest(int n) : n_(n) {
assert(n >= 0);
tr_.build(std::vector<value_type>(
std::size_t(n) + std::size_t(std::max(0, n - 1)), monoid::unit()));
end.resize(std::size_t(std::max(0, n - 1)));
}
/// @brief Insert an edge with a globally unique weight and ID. Return -1
/// when it increases the forest size; otherwise return the removed edge ID,
/// which equals id itself when the new edge is rejected.
int add_edge(int a, int b, Weight w, int id) {
assert(0 <= a && a < n_);
assert(0 <= b && b < n_);
if (!tr_.connected(a, b)) {
assert(us < std::max(0, n_ - 1));
install(us++, a, b, w, id);
return -1;
}
auto [mxw, mxi] = tr_.path_product(a, b);
if (w > mxw) {
return id;
}
int sl = its[mxi];
auto [oa, ob] = end[sl];
int ev = n_ + sl;
bool ca = tr_.cut(ev, oa);
bool cb = tr_.cut(ev, ob);
assert(ca && cb);
install(sl, a, b, w, id);
return mxi;
}
private:
int n_ = 0;
int us = 0;
link_cut_tree<monoid> tr_;
std::vector<std::pair<int, int>> end;
std::vector<int> its;
void install(int sl, int a, int b, Weight w, int id) {
assert(id >= 0);
if (int(its.size()) <= id) {
its.resize(id + 1, -1);
}
its[id] = sl;
end[sl] = {a, b};
int ev = n_ + sl;
tr_.set(ev, {w, id});
bool la = tr_.link(a, ev);
bool lb = tr_.link(b, ev);
assert(la && lb);
}
};
} // namespace noya
#endif // NOYA_INCREMENTAL_MSF_HPP
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
/// @complexity Time: Amortized O(log n) per inserted edge.
/// Space: O(n), independent of the number of rejected edges.
/// @complexity Time: Amortized O(log n) per dynamic-tree operation.
/// Space: O(n).
namespace noya {
/// @brief Link-Cut Tree for a dynamic forest with point assignment and ordered
/// path products; all operations take amortized O(log n) time.
template <class Monoid> struct link_cut_tree {
using value_type = typename Monoid::value_type;
struct node {
int ch[2] = {-1, -1};
int fa = -1;
int sz = 1;
bool rev = false;
value_type val;
value_type fwd;
value_type bwd;
explicit node(const value_type &a0) : val(a0), fwd(a0), bwd(a0) {}
};
std::vector<node> tr;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &a) { build(a); }
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &a) {
tr.clear();
tr.reserve(a.size());
st.clear();
st.reserve(a.size());
for (const value_type &val : a) {
tr.emplace_back(val);
}
}
/// @brief Return the number of vertices.
int size() const { return int(tr.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int arr, int b) {
check_vertex(arr);
check_vertex(b);
return arr == b || find_root(arr) == find_root(b);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int arr, int b) {
check_vertex(arr);
check_vertex(b);
if (connected(arr, b)) {
return false;
}
make_root(arr);
tr[arr].fa = b;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int arr, int b) {
check_vertex(arr);
check_vertex(b);
make_root(arr);
access(b);
if (tr[b].ch[0] != arr || tr[arr].ch[1] != -1) {
return false;
}
tr[b].ch[0] = -1;
tr[arr].fa = -1;
pull(b);
return true;
}
/// @brief Change one vertex value.
void set(int u, const value_type &val) {
check_vertex(u);
access(u);
tr[u].val = val;
pull(u);
}
/// @brief Return one vertex value.
const value_type &get(int u) {
check_vertex(u);
access(u);
return tr[u].val;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].fwd;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].sz;
}
private:
std::vector<int> st;
void check_vertex(int u) const { assert(0 <= u && u < size()); }
bool is_auxiliary_root(int u) const {
int fa = tr[u].fa;
return fa == -1 || (tr[fa].ch[0] != u && tr[fa].ch[1] != u);
}
int auxiliary_size(int u) const { return u == -1 ? 0 : tr[u].sz; }
value_type forward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].fwd;
}
value_type backward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].bwd;
}
void pull(int u) {
int l = tr[u].ch[0];
int r = tr[u].ch[1];
tr[u].sz = 1 + auxiliary_size(l) + auxiliary_size(r);
tr[u].fwd = Monoid::op(Monoid::op(forward_product(l), tr[u].val),
forward_product(r));
tr[u].bwd = Monoid::op(Monoid::op(backward_product(r), tr[u].val),
backward_product(l));
}
void apply_reverse(int u) {
if (u == -1) {
return;
}
std::swap(tr[u].ch[0], tr[u].ch[1]);
std::swap(tr[u].fwd, tr[u].bwd);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (!tr[u].rev) {
return;
}
apply_reverse(tr[u].ch[0]);
apply_reverse(tr[u].ch[1]);
tr[u].rev = false;
}
void rotate(int u) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
int dir = tr[fa].ch[1] == u;
int mid = tr[u].ch[dir ^ 1];
if (!is_auxiliary_root(fa)) {
tr[gp].ch[tr[gp].ch[1] == fa] = u;
}
tr[u].fa = gp;
tr[u].ch[dir ^ 1] = fa;
tr[fa].fa = u;
tr[fa].ch[dir] = mid;
if (mid != -1) {
tr[mid].fa = fa;
}
pull(fa);
pull(u);
}
void splay(int u) {
st.clear();
st.push_back(u);
for (int cur = u; !is_auxiliary_root(cur);) {
cur = tr[cur].fa;
st.push_back(cur);
}
for (auto it = st.rbegin(); it != st.rend(); ++it) {
push(*it);
}
while (!is_auxiliary_root(u)) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
if (!is_auxiliary_root(fa)) {
bool dx = tr[fa].ch[1] == u;
bool dp = tr[gp].ch[1] == fa;
rotate(dx == dp ? fa : u);
}
rotate(u);
}
}
int access(int u) {
int lst = -1;
for (int cur = u; cur != -1;) {
splay(cur);
int pp = tr[cur].fa;
tr[cur].ch[1] = lst;
if (lst != -1) {
tr[lst].fa = cur;
}
pull(cur);
lst = cur;
cur = pp;
}
splay(u);
return lst;
}
void make_root(int u) {
access(u);
apply_reverse(u);
}
int find_root(int u) {
access(u);
push(u);
while (tr[u].ch[0] != -1) {
u = tr[u].ch[0];
push(u);
}
splay(u);
return u;
}
};
} // namespace noya
namespace noya {
namespace incremental_msf_detail {
template <class Weight> struct maximum_edge_monoid {
using value_type = std::pair<Weight, int>;
static value_type unit() {
return {std::numeric_limits<Weight>::lowest(), -1};
}
static value_type op(const value_type &l, const value_type &r) {
return std::max(l, r);
}
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest under edge insertions.
/// Represent every selected edge by an extra Link-Cut Tree vertex carrying
/// (weight,id), while original vertices carry minus infinity. A cycle-forming
/// insertion exposes its endpoint path: the heaviest selected edge is replaced
/// exactly when it is heavier. Removed edge vertices are reused, so at most
/// n-1 extra nodes are needed even for an arbitrarily long insertion stream.
template <class Weight> class incremental_minimum_spanning_forest {
using monoid = incremental_msf_detail::maximum_edge_monoid<Weight>;
using value_type = typename monoid::value_type;
public:
explicit incremental_minimum_spanning_forest(int n) : n_(n) {
assert(n >= 0);
tr_.build(std::vector<value_type>(
std::size_t(n) + std::size_t(std::max(0, n - 1)), monoid::unit()));
end.resize(std::size_t(std::max(0, n - 1)));
}
/// @brief Insert an edge with a globally unique weight and ID. Return -1
/// when it increases the forest size; otherwise return the removed edge ID,
/// which equals id itself when the new edge is rejected.
int add_edge(int a, int b, Weight w, int id) {
assert(0 <= a && a < n_);
assert(0 <= b && b < n_);
if (!tr_.connected(a, b)) {
assert(us < std::max(0, n_ - 1));
install(us++, a, b, w, id);
return -1;
}
auto [mxw, mxi] = tr_.path_product(a, b);
if (w > mxw) {
return id;
}
int sl = its[mxi];
auto [oa, ob] = end[sl];
int ev = n_ + sl;
bool ca = tr_.cut(ev, oa);
bool cb = tr_.cut(ev, ob);
assert(ca && cb);
install(sl, a, b, w, id);
return mxi;
}
private:
int n_ = 0;
int us = 0;
link_cut_tree<monoid> tr_;
std::vector<std::pair<int, int>> end;
std::vector<int> its;
void install(int sl, int a, int b, Weight w, int id) {
assert(id >= 0);
if (int(its.size()) <= id) {
its.resize(id + 1, -1);
}
its[id] = sl;
end[sl] = {a, b};
int ev = n_ + sl;
tr_.set(ev, {w, id});
bool la = tr_.link(a, ev);
bool lb = tr_.link(b, ev);
assert(la && lb);
}
};
} // namespace noya