Minimum Steiner Tree (最小シュタイナー木) (graph/others/minimum-steiner-tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-08-16 01:23:21+09:00
• Include: #include "graph/others/minimum-steiner-tree.hpp"

シュタイナー木は、terminal の頂点集合を含むような木（もとのグラフの部分グラフ）です。このうち、シュタイナー木を構成する辺の重みの和が最小となる木を、最小シュタイナー木と呼びます。

最小シュタイナー木を求めることは NP 困難ですが、terminal の個数が小さい場合 $O(3^n)$ の部分集合 DP を用ることで、効率的に求めることができます。

コンストラクタ

MinimumSteinerTree<T>(const Graph<T> &g, const vector<int> &terminal)

最小シュタイナー木を求め、cost に最小シュタイナー木のコストを格納します。

副作用として dp[S][v] には terminal の頂点集合 S と頂点 v を連結にするためのコストを格納します。

それぞれについて、連結にできない場合は infty を格納します。

制約

• terminal は空でない
• terminal の各要素は $0$ 以上 $n$ 未満

計算量

• $O(n 3^t + (n + m) 2^t \log n)$

$t$ は terminal の個数です。

restore

Edges<T> restore() const

最小シュタイナー木を構成する辺集合を返します。

計算量

• $O(n)$

Depends on

• Graph Template(グラフテンプレート) (graph/graph-template.hpp)

Verified with

• test/verify/aoj-1040.test.cpp

Code

#include "../graph-template.hpp"

template <typename T>
struct MinimumSteinerTree {
  using pi = pair<int, int>;

  const T infty = numeric_limits<T>::max();

  vector<vector<T> > dp;
  T cost;

  MinimumSteinerTree() = default;

  explicit MinimumSteinerTree(const Graph<T>& g, const vector<int>& terminal)
      : g(g),
        terminal(terminal),
        dp(1 << terminal.size(), vector<T>(g.size(), infty)),
        pre(1 << terminal.size(), vector<pi>(g.size(), pi(-1, -1))) {
    assert(not terminal.empty());
    const int n = (int)g.size(), t = (int)terminal.size();
    for (int i = 0; i < t; i++) {
      assert(0 <= terminal[i] and terminal[i] < n);
      dp[1 << i][terminal[i]] = 0;
    }
    using qt = pair<T, int>;
    priority_queue<qt, vector<qt>, greater<> > que;
    for (int i = 1; i < (1 << t); i++) {
      for (int j = 0; j < n; j++) {
        for (int k = i; k > 0; k = (k - 1) & i) {
          if (dp[k][j] != infty and dp[i ^ k][j] != infty) {
            T nxt = dp[k][j] + dp[i ^ k][j];
            if (nxt < dp[i][j]) {
              dp[i][j] = nxt;
              pre[i][j] = {k, -1};
            }
          }
        }
      }
      for (int j = 0; j < n; j++) {
        if (dp[i][j] != infty) {
          que.emplace(dp[i][j], j);
        }
      }
      while (not que.empty()) {
        auto [now, v] = que.top();
        que.pop();
        if (dp[i][v] < now) continue;
        for (int j = 0; j < (int)g[v].size(); j++) {
          const auto& e = g[v][j];
          if (now + e.cost < dp[i][e.to]) {
            dp[i][e.to] = now + e.cost;
            pre[i][e.to] = {v, j};
            que.emplace(dp[i][e.to], e.to);
          }
        }
      }
    }
    cost = dp[(1 << t) - 1][terminal[0]];
  }

  Edges<T> restore() const {
    const int t = (int)terminal.size();
    assert(dp[(1 << t) - 1][terminal[0]] != infty);
    Edges<T> tree;
    vector<pair<int, int> > st;
    st.emplace_back((1 << t) - 1, terminal[0]);
    while (not st.empty()) {
      auto [x, y] = st.back();
      st.pop_back();
      if (pre[x][y].second == -1) {
        if (pre[x][y].first != -1) {
          st.emplace_back(pre[x][y].first, y);
          st.emplace_back(x ^ pre[x][y].first, y);
        }
      } else {
        tree.emplace_back(g[pre[x][y].first][pre[x][y].second]);
        st.emplace_back(x, pre[x][y].first);
      }
    }
    return tree;
  }

 private:
  const Graph<T>& g;
  const vector<int>& terminal;
  vector<vector<pi> > pre;
};

#line 2 "graph/graph-template.hpp"

template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T> >& operator[](const int& k) { return g[k]; }

  inline const vector<Edge<T> >& operator[](const int& k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;
#line 2 "graph/others/minimum-steiner-tree.hpp"

template <typename T>
struct MinimumSteinerTree {
  using pi = pair<int, int>;

  const T infty = numeric_limits<T>::max();

  vector<vector<T> > dp;
  T cost;

  MinimumSteinerTree() = default;

  explicit MinimumSteinerTree(const Graph<T>& g, const vector<int>& terminal)
      : g(g),
        terminal(terminal),
        dp(1 << terminal.size(), vector<T>(g.size(), infty)),
        pre(1 << terminal.size(), vector<pi>(g.size(), pi(-1, -1))) {
    assert(not terminal.empty());
    const int n = (int)g.size(), t = (int)terminal.size();
    for (int i = 0; i < t; i++) {
      assert(0 <= terminal[i] and terminal[i] < n);
      dp[1 << i][terminal[i]] = 0;
    }
    using qt = pair<T, int>;
    priority_queue<qt, vector<qt>, greater<> > que;
    for (int i = 1; i < (1 << t); i++) {
      for (int j = 0; j < n; j++) {
        for (int k = i; k > 0; k = (k - 1) & i) {
          if (dp[k][j] != infty and dp[i ^ k][j] != infty) {
            T nxt = dp[k][j] + dp[i ^ k][j];
            if (nxt < dp[i][j]) {
              dp[i][j] = nxt;
              pre[i][j] = {k, -1};
            }
          }
        }
      }
      for (int j = 0; j < n; j++) {
        if (dp[i][j] != infty) {
          que.emplace(dp[i][j], j);
        }
      }
      while (not que.empty()) {
        auto [now, v] = que.top();
        que.pop();
        if (dp[i][v] < now) continue;
        for (int j = 0; j < (int)g[v].size(); j++) {
          const auto& e = g[v][j];
          if (now + e.cost < dp[i][e.to]) {
            dp[i][e.to] = now + e.cost;
            pre[i][e.to] = {v, j};
            que.emplace(dp[i][e.to], e.to);
          }
        }
      }
    }
    cost = dp[(1 << t) - 1][terminal[0]];
  }

  Edges<T> restore() const {
    const int t = (int)terminal.size();
    assert(dp[(1 << t) - 1][terminal[0]] != infty);
    Edges<T> tree;
    vector<pair<int, int> > st;
    st.emplace_back((1 << t) - 1, terminal[0]);
    while (not st.empty()) {
      auto [x, y] = st.back();
      st.pop_back();
      if (pre[x][y].second == -1) {
        if (pre[x][y].first != -1) {
          st.emplace_back(pre[x][y].first, y);
          st.emplace_back(x ^ pre[x][y].first, y);
        }
      } else {
        tree.emplace_back(g[pre[x][y].first][pre[x][y].second]);
        st.emplace_back(x, pre[x][y].first);
      }
    }
    return tree;
  }

 private:
  const Graph<T>& g;
  const vector<int>& terminal;
  vector<vector<pi> > pre;
};

Back to top page