dynamic_star_min_cut.hpp¶
维护星形端点权变化下的最小割值；适合图结构固定、多个终端容量动态修改的割问题。
Complexity: Time: O(n(n+m) log n + mn) preprocessing and O(log^2 n) per update. Space: O(n+m).
AC 记录：global_minimum_cut_of_dynamic_star_augmented_graph。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n(n+m) log n + mn) preprocessing and
/// O(log^2 n) per update. Space: O(n+m).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_star_min_cut_internal {
using i64 = std::int64_t;
static constexpr i64 inf = i64(1) << 60;
class range_add_min_tree {
int siz = 1;
std::vector<i64> mn, lz;
void apply(int nd, i64 ad1) {
mn[nd] += ad1;
lz[nd] += ad1;
}
void push(int nd) {
apply(2 * nd + 1, lz[nd]);
apply(2 * nd + 2, lz[nd]);
lz[nd] = 0;
}
void add(int ql, int qr, int nd, int l, int r, i64 ad1) {
if (r <= ql || qr <= l) {
return;
}
if (ql <= l && r <= qr) {
apply(nd, ad1);
return;
}
push(nd);
int mid = (l + r) / 2;
add(ql, qr, 2 * nd + 1, l, mid, ad1);
add(ql, qr, 2 * nd + 2, mid, r, ad1);
mn[nd] = std::min(mn[2 * nd + 1], mn[2 * nd + 2]);
}
public:
explicit range_add_min_tree(int n) {
while (siz < n) {
siz *= 2;
}
mn.assign(2 * siz - 1, inf);
lz.assign(2 * siz - 1, 0);
}
void add(int l, int r, i64 ad1) { add(l, r, 0, 0, siz, ad1); }
i64 get(int i) const {
int nd = i + siz - 1;
i64 res = mn[nd];
while (nd > 0) {
nd = (nd - 1) / 2;
res += lz[nd];
}
return res;
}
void set(int i, i64 val) { add(i, i + 1, val - get(i)); }
i64 all_min() const { return mn[0]; }
};
struct weighted_neighbor {
int u;
i64 w;
};
/// Build the pendant-pair contraction tree. Each merge creates the parent of
/// its two contracted clusters, so original vertices remain the leaves.
inline std::vector<std::vector<int>>
build_contraction_tree(std::vector<std::vector<weighted_neighbor>> g) {
int n = int(g.size());
std::vector<std::vector<int>> tr(2 * n - 1);
std::vector<bool> act(2 * n - 1, true);
for (int ph = 0; ph < n - 1; ph++) {
g.push_back({});
std::vector<int> ord(n - ph);
std::vector<bool> vis(n + ph);
std::vector<i64> es(n + ph);
using heap_entry = std::pair<i64, int>;
std::priority_queue<heap_entry> q;
for (int u = 0; u < n + ph; u++) {
if (!act[u]) {
continue;
}
for (auto e : g[u]) {
es[u] += e.w;
}
q.push({-es[u], u});
}
for (int pos = 0; pos < n - ph; pos++) {
while (true) {
auto [nc, u] = q.top();
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
ord[pos] = u;
for (auto e : g[u]) {
if (!vis[e.u]) {
es[e.u] -= e.w;
q.push({-es[e.u], e.u});
}
}
break;
}
}
int a = ord[n - ph - 1];
int b = ord[n - ph - 2];
int mer = n + ph;
g[a].clear();
g[b].clear();
act[a] = act[b] = false;
for (int u = 0; u < mer; u++) {
if (!act[u]) {
continue;
}
for (weighted_neighbor &e : g[u]) {
if (e.u == a || e.u == b) {
e.u = mer;
g[mer].push_back({u, e.w});
}
}
}
tr[mer].push_back(a);
tr[mer].push_back(b);
}
return tr;
}
} // namespace dynamic_star_min_cut_internal
/// @brief Maintain the global min-cut after changing edges of an added star.
/// Repeated minimum-adjacency pendant-pair contractions build a binary cluster
/// tree with an optimal cut among its rooted clusters for every nonnegative
/// star weighting. A cluster's cut is its original-graph boundary plus the
/// star weights of its leaves. Thus a leaf update adds one value to all its
/// ancestors; heavy-light path updates and a global-min segment tree maintain
/// the best cluster cut.
class dynamic_star_min_cut {
public:
using i64 = std::int64_t;
struct edge {
int a;
int b;
i64 w;
};
private:
int nv;
std::vector<i64> wt;
std::vector<std::vector<int>> tr;
std::vector<int> fa, dep, son, hd, ord;
dynamic_star_min_cut_internal::range_add_min_tree mn;
int build_heavy(int u) {
int sz = 1;
int mc = 0;
for (int v : tr[u]) {
fa[v] = u;
dep[v] = dep[u] + 1;
int csz = build_heavy(v);
sz += csz;
if (csz > mc) {
mc = csz;
son[u] = v;
}
}
return sz;
}
void build_order(int rt) {
int ptr = 0;
std::queue<int> q;
q.push(rt);
while (!q.empty()) {
int ch = q.front();
q.pop();
for (int u = ch; u != -1; u = son[u]) {
ord[u] = ptr++;
hd[u] = ch;
for (int v : tr[u]) {
if (v != son[u]) {
q.push(v);
}
}
}
}
}
i64 add_to_ancestors(int u, i64 ad1) {
while (u >= 0) {
mn.add(ord[hd[u]], ord[u] + 1, ad1);
u = fa[hd[u]];
}
return mn.all_min();
}
public:
dynamic_star_min_cut(int n, const std::vector<edge> &es1, std::vector<i64> w0)
: nv(n), wt(std::move(w0)), tr(), fa(2 * n - 1, -1), dep(2 * n - 1),
son(2 * n - 1, -1), hd(2 * n - 1), ord(2 * n - 1, -1), mn(2 * n - 1) {
assert(n >= 1 && int(wt.size()) == n);
std::vector<std::vector<dynamic_star_min_cut_internal::weighted_neighbor>>
g(n);
for (auto [a, b, w] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(w >= 0);
if (w != 0) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
tr = dynamic_star_min_cut_internal::build_contraction_tree(g);
int rt = 2 * n - 2;
build_heavy(rt);
build_order(rt);
std::vector<i64> bd(2 * n - 1);
for (auto [a, b, w] : es1) {
if (w == 0) {
continue;
}
int l = a;
int r = b;
while (l != r) {
if (dep[l] < dep[r]) {
std::swap(l, r);
}
bd[l] += w;
l = fa[l];
}
}
for (int u = 0; u < 2 * n - 1; u++) {
mn.set(ord[u], bd[u]);
}
for (int u = 0; u < n; u++) {
assert(wt[u] >= 0);
add_to_ancestors(u, wt[u]);
}
}
/// Change one star-edge weight and return the new global minimum cut.
i64 set_star_weight(int u, i64 w) {
assert(0 <= u && u < nv && w >= 0);
i64 res = add_to_ancestors(u, w - wt[u]);
wt[u] = w;
return res;
}
i64 global_min_cut() const { return mn.all_min(); }
};
} // namespace noya
#ifndef NOYA_DYNAMIC_STAR_MIN_CUT_HPP
#define NOYA_DYNAMIC_STAR_MIN_CUT_HPP 1
/// @complexity Time: O(n(n+m) log n + mn) preprocessing and
/// O(log^2 n) per update. Space: O(n+m).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_star_min_cut_internal {
using i64 = std::int64_t;
static constexpr i64 inf = i64(1) << 60;
class range_add_min_tree {
int siz = 1;
std::vector<i64> mn, lz;
void apply(int nd, i64 ad1) {
mn[nd] += ad1;
lz[nd] += ad1;
}
void push(int nd) {
apply(2 * nd + 1, lz[nd]);
apply(2 * nd + 2, lz[nd]);
lz[nd] = 0;
}
void add(int ql, int qr, int nd, int l, int r, i64 ad1) {
if (r <= ql || qr <= l) {
return;
}
if (ql <= l && r <= qr) {
apply(nd, ad1);
return;
}
push(nd);
int mid = (l + r) / 2;
add(ql, qr, 2 * nd + 1, l, mid, ad1);
add(ql, qr, 2 * nd + 2, mid, r, ad1);
mn[nd] = std::min(mn[2 * nd + 1], mn[2 * nd + 2]);
}
public:
explicit range_add_min_tree(int n) {
while (siz < n) {
siz *= 2;
}
mn.assign(2 * siz - 1, inf);
lz.assign(2 * siz - 1, 0);
}
void add(int l, int r, i64 ad1) { add(l, r, 0, 0, siz, ad1); }
i64 get(int i) const {
int nd = i + siz - 1;
i64 res = mn[nd];
while (nd > 0) {
nd = (nd - 1) / 2;
res += lz[nd];
}
return res;
}
void set(int i, i64 val) { add(i, i + 1, val - get(i)); }
i64 all_min() const { return mn[0]; }
};
struct weighted_neighbor {
int u;
i64 w;
};
/// Build the pendant-pair contraction tree. Each merge creates the parent of
/// its two contracted clusters, so original vertices remain the leaves.
inline std::vector<std::vector<int>>
build_contraction_tree(std::vector<std::vector<weighted_neighbor>> g) {
int n = int(g.size());
std::vector<std::vector<int>> tr(2 * n - 1);
std::vector<bool> act(2 * n - 1, true);
for (int ph = 0; ph < n - 1; ph++) {
g.push_back({});
std::vector<int> ord(n - ph);
std::vector<bool> vis(n + ph);
std::vector<i64> es(n + ph);
using heap_entry = std::pair<i64, int>;
std::priority_queue<heap_entry> q;
for (int u = 0; u < n + ph; u++) {
if (!act[u]) {
continue;
}
for (auto e : g[u]) {
es[u] += e.w;
}
q.push({-es[u], u});
}
for (int pos = 0; pos < n - ph; pos++) {
while (true) {
auto [nc, u] = q.top();
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
ord[pos] = u;
for (auto e : g[u]) {
if (!vis[e.u]) {
es[e.u] -= e.w;
q.push({-es[e.u], e.u});
}
}
break;
}
}
int a = ord[n - ph - 1];
int b = ord[n - ph - 2];
int mer = n + ph;
g[a].clear();
g[b].clear();
act[a] = act[b] = false;
for (int u = 0; u < mer; u++) {
if (!act[u]) {
continue;
}
for (weighted_neighbor &e : g[u]) {
if (e.u == a || e.u == b) {
e.u = mer;
g[mer].push_back({u, e.w});
}
}
}
tr[mer].push_back(a);
tr[mer].push_back(b);
}
return tr;
}
} // namespace dynamic_star_min_cut_internal
/// @brief Maintain the global min-cut after changing edges of an added star.
/// Repeated minimum-adjacency pendant-pair contractions build a binary cluster
/// tree with an optimal cut among its rooted clusters for every nonnegative
/// star weighting. A cluster's cut is its original-graph boundary plus the
/// star weights of its leaves. Thus a leaf update adds one value to all its
/// ancestors; heavy-light path updates and a global-min segment tree maintain
/// the best cluster cut.
class dynamic_star_min_cut {
public:
using i64 = std::int64_t;
struct edge {
int a;
int b;
i64 w;
};
private:
int nv;
std::vector<i64> wt;
std::vector<std::vector<int>> tr;
std::vector<int> fa, dep, son, hd, ord;
dynamic_star_min_cut_internal::range_add_min_tree mn;
int build_heavy(int u) {
int sz = 1;
int mc = 0;
for (int v : tr[u]) {
fa[v] = u;
dep[v] = dep[u] + 1;
int csz = build_heavy(v);
sz += csz;
if (csz > mc) {
mc = csz;
son[u] = v;
}
}
return sz;
}
void build_order(int rt) {
int ptr = 0;
std::queue<int> q;
q.push(rt);
while (!q.empty()) {
int ch = q.front();
q.pop();
for (int u = ch; u != -1; u = son[u]) {
ord[u] = ptr++;
hd[u] = ch;
for (int v : tr[u]) {
if (v != son[u]) {
q.push(v);
}
}
}
}
}
i64 add_to_ancestors(int u, i64 ad1) {
while (u >= 0) {
mn.add(ord[hd[u]], ord[u] + 1, ad1);
u = fa[hd[u]];
}
return mn.all_min();
}
public:
dynamic_star_min_cut(int n, const std::vector<edge> &es1, std::vector<i64> w0)
: nv(n), wt(std::move(w0)), tr(), fa(2 * n - 1, -1), dep(2 * n - 1),
son(2 * n - 1, -1), hd(2 * n - 1), ord(2 * n - 1, -1), mn(2 * n - 1) {
assert(n >= 1 && int(wt.size()) == n);
std::vector<std::vector<dynamic_star_min_cut_internal::weighted_neighbor>>
g(n);
for (auto [a, b, w] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(w >= 0);
if (w != 0) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
tr = dynamic_star_min_cut_internal::build_contraction_tree(g);
int rt = 2 * n - 2;
build_heavy(rt);
build_order(rt);
std::vector<i64> bd(2 * n - 1);
for (auto [a, b, w] : es1) {
if (w == 0) {
continue;
}
int l = a;
int r = b;
while (l != r) {
if (dep[l] < dep[r]) {
std::swap(l, r);
}
bd[l] += w;
l = fa[l];
}
}
for (int u = 0; u < 2 * n - 1; u++) {
mn.set(ord[u], bd[u]);
}
for (int u = 0; u < n; u++) {
assert(wt[u] >= 0);
add_to_ancestors(u, wt[u]);
}
}
/// Change one star-edge weight and return the new global minimum cut.
i64 set_star_weight(int u, i64 w) {
assert(0 <= u && u < nv && w >= 0);
i64 res = add_to_ancestors(u, w - wt[u]);
wt[u] = w;
return res;
}
i64 global_min_cut() const { return mn.all_min(); }
};
} // namespace noya
#endif // NOYA_DYNAMIC_STAR_MIN_CUT_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O(n(n+m) log n + mn) preprocessing and
/// O(log^2 n) per update. Space: O(n+m).
namespace noya {
namespace dynamic_star_min_cut_internal {
using i64 = std::int64_t;
static constexpr i64 inf = i64(1) << 60;
class range_add_min_tree {
int siz = 1;
std::vector<i64> mn, lz;
void apply(int nd, i64 ad1) {
mn[nd] += ad1;
lz[nd] += ad1;
}
void push(int nd) {
apply(2 * nd + 1, lz[nd]);
apply(2 * nd + 2, lz[nd]);
lz[nd] = 0;
}
void add(int ql, int qr, int nd, int l, int r, i64 ad1) {
if (r <= ql || qr <= l) {
return;
}
if (ql <= l && r <= qr) {
apply(nd, ad1);
return;
}
push(nd);
int mid = (l + r) / 2;
add(ql, qr, 2 * nd + 1, l, mid, ad1);
add(ql, qr, 2 * nd + 2, mid, r, ad1);
mn[nd] = std::min(mn[2 * nd + 1], mn[2 * nd + 2]);
}
public:
explicit range_add_min_tree(int n) {
while (siz < n) {
siz *= 2;
}
mn.assign(2 * siz - 1, inf);
lz.assign(2 * siz - 1, 0);
}
void add(int l, int r, i64 ad1) { add(l, r, 0, 0, siz, ad1); }
i64 get(int i) const {
int nd = i + siz - 1;
i64 res = mn[nd];
while (nd > 0) {
nd = (nd - 1) / 2;
res += lz[nd];
}
return res;
}
void set(int i, i64 val) { add(i, i + 1, val - get(i)); }
i64 all_min() const { return mn[0]; }
};
struct weighted_neighbor {
int u;
i64 w;
};
/// Build the pendant-pair contraction tree. Each merge creates the parent of
/// its two contracted clusters, so original vertices remain the leaves.
inline std::vector<std::vector<int>>
build_contraction_tree(std::vector<std::vector<weighted_neighbor>> g) {
int n = int(g.size());
std::vector<std::vector<int>> tr(2 * n - 1);
std::vector<bool> act(2 * n - 1, true);
for (int ph = 0; ph < n - 1; ph++) {
g.push_back({});
std::vector<int> ord(n - ph);
std::vector<bool> vis(n + ph);
std::vector<i64> es(n + ph);
using heap_entry = std::pair<i64, int>;
std::priority_queue<heap_entry> q;
for (int u = 0; u < n + ph; u++) {
if (!act[u]) {
continue;
}
for (auto e : g[u]) {
es[u] += e.w;
}
q.push({-es[u], u});
}
for (int pos = 0; pos < n - ph; pos++) {
while (true) {
auto [nc, u] = q.top();
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
ord[pos] = u;
for (auto e : g[u]) {
if (!vis[e.u]) {
es[e.u] -= e.w;
q.push({-es[e.u], e.u});
}
}
break;
}
}
int a = ord[n - ph - 1];
int b = ord[n - ph - 2];
int mer = n + ph;
g[a].clear();
g[b].clear();
act[a] = act[b] = false;
for (int u = 0; u < mer; u++) {
if (!act[u]) {
continue;
}
for (weighted_neighbor &e : g[u]) {
if (e.u == a || e.u == b) {
e.u = mer;
g[mer].push_back({u, e.w});
}
}
}
tr[mer].push_back(a);
tr[mer].push_back(b);
}
return tr;
}
} // namespace dynamic_star_min_cut_internal
/// @brief Maintain the global min-cut after changing edges of an added star.
/// Repeated minimum-adjacency pendant-pair contractions build a binary cluster
/// tree with an optimal cut among its rooted clusters for every nonnegative
/// star weighting. A cluster's cut is its original-graph boundary plus the
/// star weights of its leaves. Thus a leaf update adds one value to all its
/// ancestors; heavy-light path updates and a global-min segment tree maintain
/// the best cluster cut.
class dynamic_star_min_cut {
public:
using i64 = std::int64_t;
struct edge {
int a;
int b;
i64 w;
};
private:
int nv;
std::vector<i64> wt;
std::vector<std::vector<int>> tr;
std::vector<int> fa, dep, son, hd, ord;
dynamic_star_min_cut_internal::range_add_min_tree mn;
int build_heavy(int u) {
int sz = 1;
int mc = 0;
for (int v : tr[u]) {
fa[v] = u;
dep[v] = dep[u] + 1;
int csz = build_heavy(v);
sz += csz;
if (csz > mc) {
mc = csz;
son[u] = v;
}
}
return sz;
}
void build_order(int rt) {
int ptr = 0;
std::queue<int> q;
q.push(rt);
while (!q.empty()) {
int ch = q.front();
q.pop();
for (int u = ch; u != -1; u = son[u]) {
ord[u] = ptr++;
hd[u] = ch;
for (int v : tr[u]) {
if (v != son[u]) {
q.push(v);
}
}
}
}
}
i64 add_to_ancestors(int u, i64 ad1) {
while (u >= 0) {
mn.add(ord[hd[u]], ord[u] + 1, ad1);
u = fa[hd[u]];
}
return mn.all_min();
}
public:
dynamic_star_min_cut(int n, const std::vector<edge> &es1, std::vector<i64> w0)
: nv(n), wt(std::move(w0)), tr(), fa(2 * n - 1, -1), dep(2 * n - 1),
son(2 * n - 1, -1), hd(2 * n - 1), ord(2 * n - 1, -1), mn(2 * n - 1) {
assert(n >= 1 && int(wt.size()) == n);
std::vector<std::vector<dynamic_star_min_cut_internal::weighted_neighbor>>
g(n);
for (auto [a, b, w] : es1) {
assert(0 <= a && a < n && 0 <= b && b < n);
assert(w >= 0);
if (w != 0) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
tr = dynamic_star_min_cut_internal::build_contraction_tree(g);
int rt = 2 * n - 2;
build_heavy(rt);
build_order(rt);
std::vector<i64> bd(2 * n - 1);
for (auto [a, b, w] : es1) {
if (w == 0) {
continue;
}
int l = a;
int r = b;
while (l != r) {
if (dep[l] < dep[r]) {
std::swap(l, r);
}
bd[l] += w;
l = fa[l];
}
}
for (int u = 0; u < 2 * n - 1; u++) {
mn.set(ord[u], bd[u]);
}
for (int u = 0; u < n; u++) {
assert(wt[u] >= 0);
add_to_ancestors(u, wt[u]);
}
}
/// Change one star-edge weight and return the new global minimum cut.
i64 set_star_weight(int u, i64 w) {
assert(0 <= u && u < nv && w >= 0);
i64 res = add_to_ancestors(u, w - wt[u]);
wt[u] = w;
return res;
}
i64 global_min_cut() const { return mn.all_min(); }
};
} // namespace noya