steiner_tree.hpp¶
用子集 DP 求连接给定终端点的最小权 Steiner 树；适合终端数量较小的图上连通代价。
Complexity: Time: O(3^k V + 2^k E log V) for k ter. Space: O(2^k V).
AC 记录：minimum_steiner_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(3^k V + 2^k E log V) for k ter.
/// Space: O(2^k V).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct steiner_tree_edge {
int a;
int b;
Weight w;
};
template <class Weight> struct steiner_tree_result {
Weight w;
std::vector<int> eid;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &es,
std::vector<int> ter) {
assert(n >= 0);
struct adjacent_edge {
int nxt;
Weight w;
int id;
};
std::vector<std::vector<adjacent_edge>> g(n);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
assert(0 <= a && a < n && 0 <= b && b < n);
assert(!(w < Weight{}));
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
for (int t : ter) {
assert(0 <= t && t < n);
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
const int k = int(ter.size());
assert(k < int(sizeof(unsigned) * 8));
if (k == 0) {
return {Weight{}, {}};
}
const Weight inf = std::numeric_limits<Weight>::max();
const int lim = 1 << k;
struct parent_record {
int sub = 0;
int pv = -1;
int ei1 = -1;
};
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
std::vector<std::vector<parent_record>> fa(lim,
std::vector<parent_record>(n));
for (int id = 0; id < k; id++) {
dis[1 << id][ter[id]] = Weight{};
}
for (int msk = 1; msk < lim; msk++) {
for (int sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
int rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf) {
continue;
}
Weight can = dis[sub][u] + dis[rhs][u];
if (can < dis[msk][u]) {
dis[msk][u] = can;
fa[msk][u] = {sub, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> q;
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) {
q.emplace(dis[msk][u], u);
}
}
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
for (auto e : g[u]) {
if (cur <= inf - e.w && cur + e.w < dis[msk][e.nxt]) {
dis[msk][e.nxt] = cur + e.w;
fa[msk][e.nxt] = {0, u, e.id};
q.emplace(dis[msk][e.nxt], e.nxt);
}
}
}
}
int rt = int(std::min_element(dis.back().begin(), dis.back().end()) -
dis.back().begin());
if (dis.back()[rt] == inf) {
return {inf, {}};
}
std::vector<bool> vis(es.size());
auto get = [&](auto &&self, int msk, int u) -> void {
parent_record rec = fa[msk][u];
if (rec.ei1 != -1) {
self(self, msk, rec.pv);
vis[rec.ei1] = true;
} else if (rec.sub != 0) {
self(self, rec.sub, u);
self(self, msk ^ rec.sub, u);
}
};
get(get, lim - 1, rt);
std::vector<int> sel;
Weight sw{};
for (int id = 0; id < int(es.size()); id++) {
if (vis[id]) {
sel.push_back(id);
sw += es[id].w;
}
}
assert(sw == dis.back()[rt]);
return {sw, std::move(sel)};
}
/// @brief Minimum weight of a connected subgraph containing all ter in
/// an undirected nonnegative-weight graph, using O(3^k n + 2^k m log n).
template <class Weight>
Weight steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &g,
std::vector<int> ter) {
const int n = int(g.size());
for (int t : ter) {
assert(0 <= t && t < n);
}
for (int u = 0; u < n; u++) {
for (auto [nxt, w] : g[u]) {
assert(0 <= nxt && nxt < n);
assert(!(w < Weight{}));
}
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
const int k = int(ter.size());
assert(k < int(sizeof(unsigned) * 8));
if (k == 0) {
return Weight{};
}
const Weight inf = std::numeric_limits<Weight>::max();
const int lim = 1 << k;
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
for (int id = 0; id < k; id++) {
dis[1 << id][ter[id]] = Weight{};
}
for (int msk = 1; msk < lim; msk++) {
for (int sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
int rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf) {
continue;
}
dis[msk][u] = std::min(dis[msk][u], dis[sub][u] + dis[rhs][u]);
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> q;
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) {
q.emplace(dis[msk][u], u);
}
}
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
for (auto [nxt, w] : g[u]) {
if (cur <= inf - w && cur + w < dis[msk][nxt]) {
dis[msk][nxt] = cur + w;
q.emplace(dis[msk][nxt], nxt);
}
}
}
}
return *std::min_element(dis.back().begin(), dis.back().end());
}
} // namespace noya
#ifndef NOYA_STEINER_TREE_HPP
#define NOYA_STEINER_TREE_HPP 1
/// @complexity Time: O(3^k V + 2^k E log V) for k ter.
/// Space: O(2^k V).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct steiner_tree_edge {
int a;
int b;
Weight w;
};
template <class Weight> struct steiner_tree_result {
Weight w;
std::vector<int> eid;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &es,
std::vector<int> ter) {
assert(n >= 0);
struct adjacent_edge {
int nxt;
Weight w;
int id;
};
std::vector<std::vector<adjacent_edge>> g(n);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
assert(0 <= a && a < n && 0 <= b && b < n);
assert(!(w < Weight{}));
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
for (int t : ter) {
assert(0 <= t && t < n);
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
const int k = int(ter.size());
assert(k < int(sizeof(unsigned) * 8));
if (k == 0) {
return {Weight{}, {}};
}
const Weight inf = std::numeric_limits<Weight>::max();
const int lim = 1 << k;
struct parent_record {
int sub = 0;
int pv = -1;
int ei1 = -1;
};
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
std::vector<std::vector<parent_record>> fa(lim,
std::vector<parent_record>(n));
for (int id = 0; id < k; id++) {
dis[1 << id][ter[id]] = Weight{};
}
for (int msk = 1; msk < lim; msk++) {
for (int sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
int rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf) {
continue;
}
Weight can = dis[sub][u] + dis[rhs][u];
if (can < dis[msk][u]) {
dis[msk][u] = can;
fa[msk][u] = {sub, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> q;
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) {
q.emplace(dis[msk][u], u);
}
}
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
for (auto e : g[u]) {
if (cur <= inf - e.w && cur + e.w < dis[msk][e.nxt]) {
dis[msk][e.nxt] = cur + e.w;
fa[msk][e.nxt] = {0, u, e.id};
q.emplace(dis[msk][e.nxt], e.nxt);
}
}
}
}
int rt = int(std::min_element(dis.back().begin(), dis.back().end()) -
dis.back().begin());
if (dis.back()[rt] == inf) {
return {inf, {}};
}
std::vector<bool> vis(es.size());
auto get = [&](auto &&self, int msk, int u) -> void {
parent_record rec = fa[msk][u];
if (rec.ei1 != -1) {
self(self, msk, rec.pv);
vis[rec.ei1] = true;
} else if (rec.sub != 0) {
self(self, rec.sub, u);
self(self, msk ^ rec.sub, u);
}
};
get(get, lim - 1, rt);
std::vector<int> sel;
Weight sw{};
for (int id = 0; id < int(es.size()); id++) {
if (vis[id]) {
sel.push_back(id);
sw += es[id].w;
}
}
assert(sw == dis.back()[rt]);
return {sw, std::move(sel)};
}
/// @brief Minimum weight of a connected subgraph containing all ter in
/// an undirected nonnegative-weight graph, using O(3^k n + 2^k m log n).
template <class Weight>
Weight steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &g,
std::vector<int> ter) {
const int n = int(g.size());
for (int t : ter) {
assert(0 <= t && t < n);
}
for (int u = 0; u < n; u++) {
for (auto [nxt, w] : g[u]) {
assert(0 <= nxt && nxt < n);
assert(!(w < Weight{}));
}
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
const int k = int(ter.size());
assert(k < int(sizeof(unsigned) * 8));
if (k == 0) {
return Weight{};
}
const Weight inf = std::numeric_limits<Weight>::max();
const int lim = 1 << k;
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
for (int id = 0; id < k; id++) {
dis[1 << id][ter[id]] = Weight{};
}
for (int msk = 1; msk < lim; msk++) {
for (int sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
int rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf) {
continue;
}
dis[msk][u] = std::min(dis[msk][u], dis[sub][u] + dis[rhs][u]);
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> q;
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) {
q.emplace(dis[msk][u], u);
}
}
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
for (auto [nxt, w] : g[u]) {
if (cur <= inf - w && cur + w < dis[msk][nxt]) {
dis[msk][nxt] = cur + w;
q.emplace(dis[msk][nxt], nxt);
}
}
}
}
return *std::min_element(dis.back().begin(), dis.back().end());
}
} // namespace noya
#endif // NOYA_STEINER_TREE_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(3^k V + 2^k E log V) for k ter.
/// Space: O(2^k V).
namespace noya {
template <class Weight> struct steiner_tree_edge {
int a;
int b;
Weight w;
};
template <class Weight> struct steiner_tree_result {
Weight w;
std::vector<int> eid;
};
/// @brief Construct a minimum Steiner tree in an undirected graph. Subset DP
/// first joins two terminal groups at a common vertex, then a multi-source
/// Dijkstra closure moves that root through the graph. Parent records replay
/// both transitions and recover the selected original edge indices.
template <class Weight>
steiner_tree_result<Weight>
steiner_tree_with_edges(int n, const std::vector<steiner_tree_edge<Weight>> &es,
std::vector<int> ter) {
assert(n >= 0);
struct adjacent_edge {
int nxt;
Weight w;
int id;
};
std::vector<std::vector<adjacent_edge>> g(n);
for (int id = 0; id < int(es.size()); id++) {
auto [a, b, w] = es[id];
assert(0 <= a && a < n && 0 <= b && b < n);
assert(!(w < Weight{}));
g[a].push_back({b, w, id});
g[b].push_back({a, w, id});
}
for (int t : ter) {
assert(0 <= t && t < n);
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
const int k = int(ter.size());
assert(k < int(sizeof(unsigned) * 8));
if (k == 0) {
return {Weight{}, {}};
}
const Weight inf = std::numeric_limits<Weight>::max();
const int lim = 1 << k;
struct parent_record {
int sub = 0;
int pv = -1;
int ei1 = -1;
};
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
std::vector<std::vector<parent_record>> fa(lim,
std::vector<parent_record>(n));
for (int id = 0; id < k; id++) {
dis[1 << id][ter[id]] = Weight{};
}
for (int msk = 1; msk < lim; msk++) {
for (int sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
int rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf) {
continue;
}
Weight can = dis[sub][u] + dis[rhs][u];
if (can < dis[msk][u]) {
dis[msk][u] = can;
fa[msk][u] = {sub, -1, -1};
}
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> q;
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) {
q.emplace(dis[msk][u], u);
}
}
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
for (auto e : g[u]) {
if (cur <= inf - e.w && cur + e.w < dis[msk][e.nxt]) {
dis[msk][e.nxt] = cur + e.w;
fa[msk][e.nxt] = {0, u, e.id};
q.emplace(dis[msk][e.nxt], e.nxt);
}
}
}
}
int rt = int(std::min_element(dis.back().begin(), dis.back().end()) -
dis.back().begin());
if (dis.back()[rt] == inf) {
return {inf, {}};
}
std::vector<bool> vis(es.size());
auto get = [&](auto &&self, int msk, int u) -> void {
parent_record rec = fa[msk][u];
if (rec.ei1 != -1) {
self(self, msk, rec.pv);
vis[rec.ei1] = true;
} else if (rec.sub != 0) {
self(self, rec.sub, u);
self(self, msk ^ rec.sub, u);
}
};
get(get, lim - 1, rt);
std::vector<int> sel;
Weight sw{};
for (int id = 0; id < int(es.size()); id++) {
if (vis[id]) {
sel.push_back(id);
sw += es[id].w;
}
}
assert(sw == dis.back()[rt]);
return {sw, std::move(sel)};
}
/// @brief Minimum weight of a connected subgraph containing all ter in
/// an undirected nonnegative-weight graph, using O(3^k n + 2^k m log n).
template <class Weight>
Weight steiner_tree(const std::vector<std::vector<std::pair<int, Weight>>> &g,
std::vector<int> ter) {
const int n = int(g.size());
for (int t : ter) {
assert(0 <= t && t < n);
}
for (int u = 0; u < n; u++) {
for (auto [nxt, w] : g[u]) {
assert(0 <= nxt && nxt < n);
assert(!(w < Weight{}));
}
}
std::sort(ter.begin(), ter.end());
ter.erase(std::unique(ter.begin(), ter.end()), ter.end());
const int k = int(ter.size());
assert(k < int(sizeof(unsigned) * 8));
if (k == 0) {
return Weight{};
}
const Weight inf = std::numeric_limits<Weight>::max();
const int lim = 1 << k;
std::vector<std::vector<Weight>> dis(lim, std::vector<Weight>(n, inf));
for (int id = 0; id < k; id++) {
dis[1 << id][ter[id]] = Weight{};
}
for (int msk = 1; msk < lim; msk++) {
for (int sub = (msk - 1) & msk; sub > 0; sub = (sub - 1) & msk) {
int rhs = msk ^ sub;
if (sub > rhs) {
continue;
}
for (int u = 0; u < n; u++) {
if (dis[sub][u] == inf || dis[rhs][u] == inf) {
continue;
}
dis[msk][u] = std::min(dis[msk][u], dis[sub][u] + dis[rhs][u]);
}
}
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<>> q;
for (int u = 0; u < n; u++) {
if (dis[msk][u] != inf) {
q.emplace(dis[msk][u], u);
}
}
while (!q.empty()) {
auto [cur, u] = q.top();
q.pop();
if (cur != dis[msk][u]) {
continue;
}
for (auto [nxt, w] : g[u]) {
if (cur <= inf - w && cur + w < dis[msk][nxt]) {
dis[msk][nxt] = cur + w;
q.emplace(dis[msk][nxt], nxt);
}
}
}
}
return *std::min_element(dis.back().begin(), dis.back().end());
}
} // namespace noya