AIOJ

The Steiner tree problem is a combinatorial optimization problem, similar to the minimum spanning tree problem, and asks for a shortest network. A minimum spanning tree seeks the shortest network connecting all vertices in a given set using given edges. A minimum Steiner tree may add vertices outside the given set so that the resulting network has minimum cost.

Introduction

In the early nineteenth century, the renowned Berlin mathematician Steiner studied a simple but enlightening problem: connect three villages with roads of minimum total length. Mathematically, given three points $A$ , $B$ , and $C$ in the plane, find a fourth point $P$ such that $a+b+c$ is minimized, where $a$ , $b$ , and $c$ are the distances from $P$ to $A$ , $B$ , and $C$ , respectively.

If every interior angle of triangle $\textit{ABC}$ is less than $120^{\circ}$ , then $P$ is the point from which the segments $\textit{AB}$ , $\textit{BC}$ , and $\textit{AC}$ subtend angles of $120^{\circ}$ . If one angle of triangle $\textit{ABC}$ , say angle $C$ , is at least $120^{\circ}$ , then $P$ coincides with vertex $C$ .

Generalizations

The Steiner problem starts with three fixed points $A,B,C$ . It is natural to generalize it to $n$ points $A_1,A_2,\dots,A_n$ : find a point $P$ in the plane minimizing $a_1+a_2+\dots+a_n$ , where $a_i$ is the distance $PA_i$ .
We can also include weights. The other factors associated with the $n$ points can be represented by weights; find a point $P$ minimizing $a_1\cdot w_1+a_2\cdot w_2+\dots+a_n\cdot w_n$ , where $w_i$ is the weight of each point.
Courant (R. Courant) and Robbins (H. Robbins) observed that the first generalization is superficial. A genuinely useful generalization must abandon the search for a single point $P$ and instead seek a road network of minimum total length. Given $n$ points $A_1,A_2,\cdots,A_n$ , find a shortest system of line segments connecting these $n$ points such that every pair can be connected by a polygonal path made from those segments. They called this the Steiner tree problem. For $n$ given points there are at most $n-2$ junctions (Steiner points). At most three edges pass through each Steiner point. If there are three, their pairwise angles are $120^{\circ}$ ; if there are two, the Steiner point must be one of the given points and the angle between the two edges is at least $120^{\circ}$ .

Shortest network connecting more than three points

steiner-tree1

In the first case, the solution consists of five segments and has two Steiner points (the red $s_1,s_2$ ), where three segments meet at pairwise angles of $120^{\circ}$ . The second solution has three Steiner points. In the third case, one or more Steiner points may degenerate or be replaced by one or more given points.

We now express the Steiner tree problem in graph-theoretic form.

steiner-tree2

In the first graph, if the terminals are $\{1,2,3,4\}$ , directly connecting them has minimum total edge weight 12, which is clearly not optimal. If vertex 5 is allowed, the minimum total becomes 9, giving a better answer.

In the second graph, some of the terminals $\{1,2,3,4\}$ are not even joined by direct edges, so Steiner points must be considered. Including vertex 5 gives a minimum total edge weight of 9.

In both graphs, the Steiner point for vertices 1 and 4 is degenerate: it is replaced by vertex 1 or vertex 4.

Example

Let us begin with a standard problem to familiarize ourselves with the minimum Steiner tree. See Template: Minimum Steiner Tree.

The statement is clear: given a connected graph $G$ with $n$ vertices and $k$ terminals, connect the $k$ terminals so that the sum of the weights of all edges in the resulting tree is minimized.

From the discussion above, directly connecting the $k$ terminals need not be optimal; in fact, some of the $k$ terminals may not be directly adjacent. Therefore, the remaining $n-k$ vertices should also be considered.

Use a state-compressed dynamic program. Let $f(i,S)$ be the minimum total edge weight of a tree rooted at $i$ and containing every vertex in $S$ .

Consider the transitions:

First merge connected subsets: $f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T))$ .
Under the current connected-subset state, relax edges: $f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))$ . In the code below, tree[tot] records the information associated with the two adjacent vertices $i,j$ .

Reference implementation

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

constexpr int MAXN = 510;
constexpr int INF = 0x3f3f3f3f;
using P = pair<int, int>;
int n, m, k;

struct edge {
  int to, next, w;
} e[MAXN << 1];

int head[MAXN << 1], tree[MAXN << 1], tot;
int dp[MAXN][5000], vis[MAXN];
int key[MAXN];
priority_queue, greater> q;

void add(int u, int v, int w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void dijkstra(int s) {  // solve shortest paths
  memset(vis, 0, sizeof(vis));
  while (!q.empty()) {
    P item = q.top();
    q.pop();
    if (vis[item.second]) continue;
    vis[item.second] = 1;
    for (int i = head[item.second]; i; i = e[i].next) {
      if (dp[tree[i]][s] > dp[item.second][s] + e[i].w) {
        dp[tree[i]][s] = dp[item.second][s] + e[i].w;
        q.push(P(dp[tree[i]][s], tree[i]));
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  memset(dp, INF, sizeof(dp));
  cin >> n >> m >> k;
  int u, v, w;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    add(u, v, w);
    tree[tot] = v;
    add(v, u, w);
    tree[tot] = u;
  }
  for (int i = 1; i <= k; i++) {
    cin >> key[i];
    dp[key[i]][1 << (i - 1)] = 0;
  }
  for (int s = 1; s < (1 << k); s++) {
    for (int i = 1; i <= n; i++) {
      for (int subs = s & (s - 1); subs;
           subs = s & (subs - 1))  // see the detailed state-compression DP explanation
        dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]);
      if (dp[i][s] != INF) q.push(P(dp[i][s], i));
    }
    dijkstra(s);
  }
  cout << dp[key[1]][(1 << k) - 1] << '\n';
  return 0;
}

Another classic example is [WC2008] Travel Plan.

This problem asks for a Steiner tree with minimum total vertex weight. Let $f(i,S)$ be the minimum total vertex weight of a tree rooted at $i$ and containing all vertices in $S$ , and let $a_i$ be the vertex weight.

Consider the transitions:

$f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T)-a_i)$ . The same vertex weight $a_i$ is counted twice when the states are merged, so subtract it once.
$f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))$ .

The transitions are similar to those in the template problem. The difficult part is outputting the answer: the path must also be recorded during the DP.

Use pre[i][s] to record the vertex and subset information for a state rooted at $i$ with connected subset $s$ . After the DP, start from pre[root][S], find the vertices connected to the vertices in the subset, and repeatedly split $S$ . Record the selected vertices in ans; the search ends when the subset has been fully decomposed.

Reference implementation

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define mp make_pair
using P = pair<int, int>;
using PP = pair;
constexpr int INF = 0x3f3f3f3f;
constexpr int dx[] = {0, 0, -1, 1};
constexpr int dy[] = {1, -1, 0, 0};
int n, m, K, root;
int f[101][1111], a[101], ans[11][11];
bool inq[101];
PP pre[101][1111];
queue q;

bool legal(P u) {
  if (u.first >= 0 && u.second >= 0 && u.first < n && u.second < m) {
    return true;
  }
  return false;
}

int num(P u) { return u.first * m + u.second; }

void spfa(int s) {
  memset(inq, 0, sizeof(inq));
  while (!q.empty()) {
    P u = q.front();
    q.pop();
    inq[num(u)] = false;
    for (int d = 0; d < 4; d++) {
      P v = mp(u.first + dx[d], u.second + dy[d]);
      int du = num(u), dv = num(v);
      if (legal(v) && f[dv][s] > f[du][s] + a[dv]) {
        f[dv][s] = f[du][s] + a[dv];
        if (!inq[dv]) {
          inq[dv] = true;
          q.push(v);
        }
        pre[dv][s] = mp(u, s);
      }
    }
  }
}

void dfs(P u, int s) {
  if (!pre[num(u)][s].second) return;
  ans[u.first][u.second] = 1;
  int nu = num(u);
  if (pre[nu][s].first == u)
    dfs(u, s ^ pre[nu][s].second);  // use DFS to recover the answer
  dfs(pre[nu][s].first, pre[nu][s].second);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  memset(f, INF, sizeof(f));
  cin >> n >> m;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[tot];
      if (!a[tot]) {
        f[tot][1 << (K++)] = 0;
        root = tot;
      }
      tot++;
    }
  }
  for (int s = 1; s < (1 << K); s++) {
    for (int i = 0; i < n * m; i++) {
      for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) {
        if (f[i][s] > f[i][subs] + f[i][s ^ subs] - a[i]) {
          f[i][s] = f[i][subs] + f[i][s ^ subs] - a[i];  // state transition
          pre[i][s] = mp(mp(i / m, i % m), subs);
        }
      }
      if (f[i][s] < INF) q.push(mp(i / m, i % m));
    }
    spfa(s);
  }
  cout << f[root][(1 << K) - 1] << '\n';
  dfs(mp(root / m, root % m), (1 << K) - 1);
  for (int i = 0, tot = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (!a[tot++])
        cout << 'x';
      else
        cout << (ans[i][j] ? 'o' : '_');
    }
    if (i != n - 1) cout << '\n';
  }
  return 0;
}

Steiner Trees

Introduction

Generalizations

Example

Exercises