斯坦納樹

斯坦納樹問題是組合優化問題，與最小生成樹相似，是最短網絡的一種。最小生成樹是在給定的點集和邊中尋求最短網絡使所有點連通。而最小斯坦納樹允許在給定點外增加額外的點，使生成的最短網絡開銷最小。

問題引入

19 世紀初葉，柏林大學幾何方面的著名學者斯坦納，研究了一個非常簡單卻很有啓示性的問題：將三個村莊用總長為極小的道路連接起來。從數學上説，就是在平面內給定三個點 \(A\)、\(B\)、\(C\) 找出平面內第四個點 \(P\)，使得和數 \(a+b+c\) 為最短，這裏 \(a\)、\(b\)、\(c\) 分別表示從 \(P\) 到 \(A\)、\(B\)、\(C\) 的距離。

問題的答案是：如果三角形 \(\textit{ABC}\) 的每個內角都小於 \(120^{\circ}\)，那麼 \(P\) 就是使邊 \(\textit{AB}\)、\(\textit{BC}\)、\(\textit{AC}\) 對該點所張的角都是 \(120^{\circ}\) 的點。如果三角形 \(\textit{ABC}\) 的有一個角，例如 \(C\) 角，大於或等於 \(120^{\circ}\)，那麼點 \(P\) 與頂點 \(C\) 重合。

問題推廣

1. 在斯坦納問題中，給定了三個固定點 \(A,B,C\)。很自然地可以把這個問題推廣到給定 \(n\) 個點 \(A_1,A_2,\dots,A_n\) 的情形；我們要求出平面內的點 \(P\)，使距離和 \(a_1+a_2+\dots+a_n\) 為極小，其中 \(a_i\) 是距離 \(PA_i\)。

2. 考慮到點的其他相關因素，加入了權重的表示。\(n\) 個點的其他相關因素可以換算成一個權重表示，求出平面內的點 \(P\)，使距離與權重的乘積的總和 \(a_1\cdot w_1+a_2\cdot w_2+\dots+a_n\cdot w_n\) 為極小，其中 \(w_i\) 是每個點的權重。

3. 庫朗（R.Courant）和羅賓斯（H.Robbins）提出第一個定義的推廣是膚淺的。為了求得斯坦納問題真正有價值的推廣，必須放棄尋找一個單獨的點 \(P\)，而代之以具有最短總長的＂道路網＂。數學上表述成：給定 \(n\) 個點 \(A_1,A_2,\cdots,A_n\)，試求連接此 \(n\) 個點，總長最短的直線段連接系統，並且任意兩點都可由系統中的直線段組成的折線連接起來。他們將此新問題稱為 斯坦納樹問題。在給定 \(n\) 個點的情形，最多將有 \(n-2\) 個復接點（斯坦納點）。過每一斯坦納點，至多有三條邊通過。若為三條邊，則它們兩兩交成 \(120^{\circ}\) 角；若為兩條邊，則此斯坦納點必為某一已給定的點，且此兩條邊交成的角必大於或等於 \(120^{\circ}\)。

連接三個以上的點的最短網絡

在第一種情形，解是由五條線段組成的，其中有兩個斯坦納點（紅色 \(s_1,s_2\)），在那裏有三條線段相交且相互間的交角為 \(120^{\circ}\)。第二種情形的解含有三個斯坦納點。第三種情形，一個或幾個斯坦納點可能退化，或被一個或幾個給定的點所代替。

我們將斯坦納樹的問題模型以圖論形式呈現。

對於形式一，如果令關鍵點為 \(\{1,2,3,4\}\)，可以發現若直接將這四個關鍵點相連的最小邊權和是 12，顯然這不是最優的。如果考慮使用 5 號節點那麼最小邊權和就會是 9，得到一個更優的答案。

對於形式二，如果令關鍵點為 \(\{1,2,3,4\}\)，可以發現這四個關鍵點中的一些點甚至沒有直接相連的邊，必須考慮使用復接點（斯坦納點）。這時將 5 號考慮進去可以得到最小邊權和 9。

並且我們可以發現在兩張圖中 1 號和 4 號的斯坦納點是退化的，被 1 號或 4 號代替了。

例題

首先以一道模板題來帶大家熟悉最小斯坦納樹問題。見 【模板】最小斯坦納樹。

題意已經很明確了，給定連通圖 \(G\) 中的 \(n\) 個點與 \(k\) 個關鍵點，連接 \(k\) 個關鍵點，使得生成樹的所有邊的權值和最小。

結合上面的知識我們可以知道直接連接這 \(k\) 個關鍵點生成的權值和不一定是最小的，或者這 \(k\) 個關鍵點不會直接（相鄰）連接。所以應當使用剩下的 \(n-k\) 個點。

我們使用狀態壓縮動態規劃來求解。用 \(f(i,S)\) 表示以 \(i\) 為根的一棵樹，包含集合 \(S\) 中所有點的最小邊權值和。

考慮狀態轉移：

• 首先對連通的子集進行轉移，\(f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T))\)。

• 在當前的子集連通狀態下進行邊的鬆弛操作，\(f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))\)。在下面的代碼中用一個 tree[tot] 來記錄兩個相連節點 \(i,j\) 的相關信息。

參考實現

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
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<P, vector<P>, greater<P> > q;

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

void dijkstra(int s) {  // 求解最短路
  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() {
  memset(dp, INF, sizeof(dp));
  scanf("%d %d %d", &n, &m, &k);
  int u, v, w;
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d", &u, &v, &w);
    add(u, v, w);
    tree[tot] = v;
    add(v, u, w);
    tree[tot] = u;
  }
  for (int i = 1; i <= k; i++) {
    scanf("%d", &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))  // 状压 dp 可以看下题解里写的比较详细
        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);
  }
  printf("%d\n", dp[key[1]][(1 << k) - 1]);
  return 0;
}

另外一道經典例題 [WC2008] 遊覽計劃。

這道題是求點權和最小的斯坦納樹，用 \(f(i,S)\) 表示以 \(i\) 為根的一棵樹，包含集合 \(S\) 中所有點的最小點權值和。\(a_i\) 表示點權。

考慮狀態轉移：

• \(f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T)-a_i)\)。由於此處合併時同一個點 \(a_i\)，會被加兩次，所以減去。

• \(f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))\)。

可以發現狀態轉移與上面的模板題是類似的，麻煩的是對答案的輸出，在 DP 的過程中還要記錄路徑。

用 pre[i][s] 記錄轉移到 \(i\) 為根，連通狀態集合為 \(s\) 時的點與集合的信息。在 DP 結束後從 pre[root][S] 出發，尋找與集合裏的點相連的那些點並逐步分解集合 \(S\)，用 ans 數組來記錄被使用的那些點，當集合分解完畢時搜索也就結束了。

參考實現

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
typedef pair<int, int> P;
typedef pair<P, int> PP;
const int INF = 0x3f3f3f3f;
const int dx[] = {0, 0, -1, 1};
const 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<P> 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)] = 0;
    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] = 1;
          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);  // 通过 dfs 来找到答案
  dfs(pre[nu][s].first, pre[nu][s].second);
}

int main() {
  memset(f, INF, sizeof(f));
  scanf("%d %d", &n, &m);
  int tot = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &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];  // 状态转移
          pre[i][s] = mp(mp(i / m, i % m), subs);
        }
      }
      if (f[i][s] < INF) q.push(mp(i / m, i % m));
    }
    spfa(s);
  }
  printf("%d\n", f[root][(1 << K) - 1]);
  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++])
        putchar('x');
      else
        putchar(ans[i][j] ? 'o' : '_');
    }
    if (i != n - 1) printf("\n");
  }
  return 0;
}

習題

• 【模板】最小斯坦納樹
• [WC2008] 遊覽計劃
• [JLOI2015] 管道連接
• [APIO2013] 機器人

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用