Wiki › Thuật toán › Hình học tính toán › Cây Steiner

Cây Steiner

huunguyen Updated Tháng 9. 30, 2026 Đọc 25 phút 18 lượt xem

Cây Steiner (Steiner tree) là bài toán: cho một đồ thị có trọng số (hoặc một tập điểm trên mặt phẳng) và $k$ đỉnh bắt buộc gọi là terminal, hãy nối tất cả terminal bằng một cây có tổng trọng số nhỏ nhất, trong đó được phép đi qua (dùng thêm) các đỉnh khác. Bài toán tổng quát là NP-khó, nhưng khi $k$ nhỏ (thường $k \leq 10$ ) có một lời giải quy hoạch động chính xác chạy trong $O (3^{k} \cdot n + 2^{k} \cdot m \log m)$ , thay vì duyệt mọi tập đỉnh trung gian trong $O (2^{n})$ . Với $k = 3$ còn có công thức gọn hơn nữa: chỉ cần $3$ lần BFS/Dijkstra rồi thử mọi điểm gặp nhau.

Ý tưởng / Trực giác

Khác gì cây khung nhỏ nhất?

Cây khung nhỏ nhất (MST) phải nối mọi đỉnh và chỉ được dùng các đỉnh đó. Cây Steiner chỉ bắt buộc nối $k$ terminal, nhưng lại được mượn đỉnh trung gian (gọi là điểm Steiner) nếu việc đó làm cây ngắn đi.

Cách làm "ngây thơ" thường gặp là: tính khoảng cách ngắn nhất giữa mọi cặp terminal, rồi dựng MST trên $k$ terminal với các khoảng cách đó. Cách này sai, và có thể tệ gần 2 lần. Xét đồ thị hình sao: một đỉnh tâm $X$ nối với $k$ terminal, mỗi cạnh dài $1$ .

          T1
          |1
   T4 --1-X-1-- T2        khoảng cách giữa hai terminal bất kỳ = 2
          |1              MST trên terminal : (k-1) * 2 = 2k - 2
          T3              cây Steiner (dùng X): k * 1  = k

Tỉ lệ là $\frac{2 k - 2}{k} \to 2$ . Ngược lại, người ta chứng minh được MST trên các khoảng cách ngắn nhất không bao giờ tệ hơn $2 (1 - 1 / k)$ lần, nên đó là một thuật toán xấp xỉ tốt khi $k$ lớn, nhưng không phải đáp án đúng.

Trạng thái DP: "cây nối tập terminal $S$ và có chứa đỉnh $v$ "

Đánh số terminal $0 . . k - 1$ và biểu diễn một tập terminal bằng mặt nạ bit (xem DP bitmask). Định nghĩa

$d p [mask] [v] = tổng trọng số nhỏ nhất của một cây chứa đỉnh v và mọi terminal trong mask.$

Đáp án là ${min}_{v} d p [full] [v]$ (thật ra với mọi $v$ thuộc cây tối ưu, giá trị đều bằng đáp án). Khởi tạo $d p [{i}] [t_{i}] = 0$ .

Vì sao chỉ cần hai loại chuyển trạng thái? Lấy một cây tối ưu $T$ cho $(mask, v)$ có ít cạnh nhất, tức là đã cắt hết các lá không phải terminal và khác $v$ (trọng số không âm nên cắt không làm cây dài thêm; điều này quan trọng khi có cạnh trọng số $0$ ). Khi đó mọi nhánh tại $v$ đều chứa ít nhất một terminal. Treo $T$ tại $v$ . Có hai khả năng:

$v$ có từ hai nhánh con trở lên. Cắt $T$ tại $v$ thành hai cây con cùng chứa $v$ : một cây gồm một nhánh, cây kia gồm các nhánh còn lại. Các terminal của mask bị chia thành hai tập rời nhau $sub$ và $mask ⧵ sub$ (terminal nằm đúng tại $v$ thì gán cho một bên tùy ý). Hai cây con không chung cạnh nào, nên $d p [mask] [v] = d p [sub] [v] + d p [mask \oplus sub] [v] .$ Đây là chuyển gộp (merge): duyệt mọi tập con thật sự khác rỗng của mask.
$v$ chỉ có đúng một nhánh, đi qua cạnh $(v, u)$ trọng số $w$ . Bỏ $v$ và cạnh đó, phần còn lại là một cây chứa $u$ và mọi terminal của mask (nếu $v$ là terminal $i$ thì nó được "bao" bởi trường hợp 1 với $sub = {i}$ , vì $d p [{i}] [t_{i}] = 0$ ). Vậy $d p [mask] [v] = d p [mask] [u] + w .$ Đây là chuyển lan theo cạnh (extend).

Chuyển gộp chỉ dùng các mask nhỏ hơn (tập con thật sự), nên với từng mask theo thứ tự tăng dần, ta làm gộp trước. Sau đó chuyển lan theo cạnh là một hệ "khoảng cách ngắn nhất" với các giá trị ban đầu khác nhau ở mỗi đỉnh: chính là Dijkstra đa nguồn, đẩy mọi $v$ có $d p [mask] [v] < \infty$ vào hàng đợi cùng lúc. Trọng số không âm nên Dijkstra đúng.

Có thể hình dung như sau: mỗi terminal là một "giọt mực" loang ra theo Dijkstra. Hai vết mực (hai tập terminal) gặp nhau tại một đỉnh thì hòa thành một vết mực lớn hơn, rồi vết mực mới đó lại tiếp tục loang.

Tại sao không bỏ sót cây nào?

Mỗi cây tối ưu có hữu hạn đỉnh; quy nạp theo (số terminal, số cạnh): tại gốc $v$ hoặc tách được thành hai cây nhỏ hơn về số terminal (chuyển 1), hoặc bớt được một cạnh mà giữ nguyên tập terminal (chuyển 2). Ngược lại, mọi giá trị DP tạo ra đều ứng với một đồ thị con liên thông chứa đủ terminal có trọng số đúng bằng giá trị đó (hai cây gộp lại có thể trùng cạnh, khi đó trọng số thật còn nhỏ hơn). Nên DP không bao giờ cho đáp án nhỏ hơn đáp án thật, và đạt được đáp án thật.

Ví dụ chạy tay

Đồ thị 5 đỉnh, terminal $A, B, C$ (bit $0, 1, 2$ ), hai đỉnh trung gian $X, Y$ :

     A ---------3--------- B
      \                  / |
     2 \              2 /  |
        \              /   | 5
         `---- X -----'    |
               |           |
             1 |           |
               Y ----1---- C

Cạnh: A-B:3  A-X:2  B-X:2  X-Y:1  Y-C:1  B-C:5

Khoảng cách ngắn nhất giữa các terminal: $d (A, B) = 3$ , $d (A, C) = 4$ , $d (B, C) = 4$ . MST trên terminal cho $3 + 4 = 7$ . Cây Steiner thật dùng $X, Y$ : $A - X$ , $B - X$ , $X - Y$ , $Y - C$ có tổng $2 + 2 + 1 + 1 = 6$ .

Mask đơn ( ${A}$ , ${B}$ , ${C}$ ): không có gì để gộp, Dijkstra từ đúng terminal đó, tức $d p [{i}] [v]$ là khoảng cách từ $t_{i}$ tới $v$ .

Mask ${A, B}$ (mask $= 3$ ). Gộp tại từng đỉnh: $d p [{A}] [v] + d p [{B}] [v]$ :

đỉnh      A    B    C    X    Y
{A}       0    3    4    2    3
{B}       3    0    4    2    3
gộp       3    3    8    4    6      <- sau bước gộp
Dijkstra  3    3    6    4    5      <- Y: 4+1 (từ X) ; C: 5+1 (từ Y)

Ô $Y$ giảm từ $6$ xuống $5$ : cây tốt nhất nối $A, B$ và chứa $Y$ không phải là "đường $A \to Y$ cộng đường $B \to Y$ " (hai đường đó trùng đoạn $X - Y$ ), mà là cây $A - X - B$ rồi kéo thêm cạnh $X - Y$ . Đó đúng là lý do cần bước lan theo cạnh sau bước gộp.

Bảng đầy đủ:

mask	A	B	C	X	Y
${A}$	0	3	4	2	3
${B}$	3	0	4	2	3
${A, B}$	3	3	6	4	5
${C}$	4	4	0	2	1
${A, C}$	4	6	4	4	4
${B, C}$	6	4	4	4	4
${A, B, C}$	6	6	6	6	6

Mask ${A, B, C}$ tại $X$ : ba cách chia (chỉ xét $sub$ chứa bit thấp nhất là $A$ để mỗi cách chia được thử một lần):

{A} + {B,C}  : 2 + 4 = 6
{A,B} + {C}  : 4 + 2 = 6
{A,C} + {B}  : 4 + 2 = 6

Tại $Y$ : ${A, B} + {C} = 5 + 1 = 6$ (hai cách còn lại cho $7$ ). Đáp án ${min}_{v} d p [full] [v] = 6$ , nhỏ hơn $7$ của MST trên terminal.

Cài đặt

C++: DP $d p [mask] [v]$ trên đồ thị

Code dưới đây đã được đối chiếu với lời giải vét cạn (thử mọi tập đỉnh $S$ chứa các terminal, lấy MST của đồ thị con cảm sinh bởi $S$ ) trên $3000$ đồ thị ngẫu nhiên đến $9$ đỉnh, $5$ terminal, có cả trường hợp không liên thông.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;

// Minimum Steiner tree: connect all terminals, extra vertices allowed.
// n vertices (0-indexed), adj[v] = {(u, w)}, w >= 0.
ll steinerTree(int n, const vector<vector<pair<int,ll>>>& adj,
               const vector<int>& term) {
    int k = term.size();
    if (k <= 1) return 0;
    int full = (1 << k) - 1;
    vector<vector<ll>> dp(1 << k, vector<ll>(n, INF));
    for (int i = 0; i < k; i++) dp[1 << i][term[i]] = 0;

    for (int mask = 1; mask <= full; mask++) {
        vector<ll>& cur = dp[mask];
        // Transition 1: merge two disjoint parts meeting at the same vertex v.
        // Only sub containing the lowest bit, so each split is tried once.
        int low = mask & -mask;
        for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
            if (!(sub & low)) continue;
            const vector<ll>& A = dp[sub];
            const vector<ll>& B = dp[mask ^ sub];
            for (int v = 0; v < n; v++)
                if (A[v] < INF && B[v] < INF)
                    cur[v] = min(cur[v], A[v] + B[v]);
        }
        // Transition 2: extend along edges (Dijkstra, all v are sources).
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        for (int v = 0; v < n; v++)
            if (cur[v] < INF) pq.push({cur[v], v});
        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d != cur[v]) continue;          // stale entry
            for (auto [u, w] : adj[v])
                if (d + w < cur[u]) { cur[u] = d + w; pq.push({cur[u], u}); }
        }
    }
    ll ans = INF;
    for (int v = 0; v < n; v++) ans = min(ans, dp[full][v]);
    return ans;                                  // INF if terminals disconnected
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int,ll>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; ll w; cin >> u >> v >> w; u--; v--;
        adj[u].push_back({v, w}); adj[v].push_back({u, w});
    }
    vector<int> term(k);
    for (int& t : term) { cin >> t; t--; }
    ll ans = steinerTree(n, adj, term);
    if (ans >= INF) cout << -1 << '\n'; else cout << ans << '\n';
}

Input của ví dụ chạy tay (đánh số $A = 1, B = 2, C = 3, X = 4, Y = 5$ ) cho kết quả 6:

Python

Cùng thuật toán, tiện để thử ý tưởng với $n$ nhỏ (với $n$ cỡ $10^{3}$ trở lên và $k \geq 8$ thì nên dùng C++).

import sys, heapq

def steiner_tree(n, adj, term):
    """adj[v] = list of (u, w); returns min total weight, or None if impossible."""
    k = len(term)
    if k <= 1:
        return 0
    INF = float('inf')
    full = (1 << k) - 1
    dp = [[INF] * n for _ in range(1 << k)]
    for i, t in enumerate(term):
        dp[1 << i][t] = 0
    for mask in range(1, full + 1):
        cur = dp[mask]
        low = mask & -mask
        sub = (mask - 1) & mask
        while sub:
            if sub & low:  # try each unordered split once
                a, b = dp[sub], dp[mask ^ sub]
                for v in range(n):
                    s = a[v] + b[v]
                    if s < cur[v]:
                        cur[v] = s
            sub = (sub - 1) & mask
        pq = [(d, v) for v, d in enumerate(cur) if d < INF]
        heapq.heapify(pq)
        while pq:
            d, v = heapq.heappop(pq)
            if d != cur[v]:
                continue
            for u, w in adj[v]:
                if d + w < cur[u]:
                    cur[u] = d + w
                    heapq.heappush(pq, (cur[u], u))
    ans = min(dp[full])
    return None if ans == INF else ans

def main():
    data = sys.stdin.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    adj = [[] for _ in range(n)]
    p = 3
    for _ in range(m):
        u, v, w = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2])
        p += 3
        adj[u].append((v, w))
        adj[v].append((u, w))
    term = [int(x) - 1 for x in data[p:p + k]]
    ans = steiner_tree(n, adj, term)
    print(-1 if ans is None else ans)

main()

Cây Steiner trên lưới (trọng số trên ô)

Trên lưới, "đỉnh" là ô và chi phí thường đặt trên ô chứ không trên cạnh: xây đường qua ô $(r, c)$ tốn $c o s t [r] [c]$ , ô cấm đi thì bỏ qua. DP giữ nguyên, chỉ đổi hai chỗ:

$d p [mask] [v]$ đã tính cả chi phí ô $v$ . Khi gộp hai cây cùng chứa $v$ , ô $v$ bị đếm hai lần nên phải trừ đi một lần: $d p [sub] [v] + d p [mask \oplus sub] [v] - c o s t [v]$ .
Bước lan: đi từ ô $v$ sang ô kề $u$ tốn $c o s t [u]$ (trọng số "trên đỉnh đích"), 4 hướng như BFS trên lưới.

Code đã so với vét cạn mọi tập ô (lưới tới $3 \times 4$ , tới $4$ terminal, có ô cấm) trên $2000$ bộ ngẫu nhiên.

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;

// Grid Steiner tree with cell costs: choose a 4-connected set of cells
// containing all terminals, minimizing the total cost of chosen cells.
// cost[r][c] >= 0, cost = -1 means blocked.
int main() {
    int R, C, k;
    cin >> R >> C >> k;
    int n = R * C;
    vector<int> cost(n);
    for (int& x : cost) cin >> x;
    vector<int> term(k);
    for (int i = 0; i < k; i++) { int r, c; cin >> r >> c; term[i] = r * C + c; }
    for (int t : term)
        if (cost[t] < 0) { cout << -1 << '\n'; return 0; }   // terminal on a blocked cell

    int full = (1 << k) - 1;
    vector<vector<int>> dp(1 << k, vector<int>(n, INF));
    for (int i = 0; i < k; i++) dp[1 << i][term[i]] = cost[term[i]];
    const int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

    for (int mask = 1; mask <= full; mask++) {
        vector<int>& cur = dp[mask];
        int low = mask & -mask;
        for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
            if (!(sub & low)) continue;
            for (int v = 0; v < n; v++)
                if (dp[sub][v] < INF && dp[mask ^ sub][v] < INF)
                    // cell v is in both parts: count its cost once
                    cur[v] = min(cur[v], dp[sub][v] + dp[mask ^ sub][v] - cost[v]);
        }
        // Dijkstra: stepping into cell u costs cost[u]
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        for (int v = 0; v < n; v++) if (cur[v] < INF) pq.push({cur[v], v});
        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d != cur[v]) continue;
            int r = v / C, c = v % C;
            for (int t = 0; t < 4; t++) {
                int nr = r + dr[t], nc = c + dc[t];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                int u = nr * C + nc;
                if (cost[u] < 0) continue;            // blocked cell
                if (d + cost[u] < cur[u]) { cur[u] = d + cost[u]; pq.push({cur[u], u}); }
            }
        }
    }
    int ans = INF;
    for (int v = 0; v < n; v++) ans = min(ans, dp[full][v]);
    cout << (ans >= INF ? -1 : ans) << '\n';
}

Input: dòng đầu R C k, sau đó $R \cdot C$ số chi phí theo từng hàng ( $- 1$ là ô cấm), rồi $k$ dòng r c (đánh số từ $0$ ). Nếu có terminal nằm trên ô cấm thì không có lời giải, code in $- 1$ .

Trường hợp đặc biệt: 3 terminal

Với $k = 3$ không cần DP bitmask. Có thể coi mọi lá của cây tối ưu đều là terminal (lá không phải terminal thì cắt đi, trọng số không âm nên cây không dài thêm). Cây như vậy có tối đa $3$ lá (mọi lá là terminal) nên:

hoặc là một đường đi, terminal ở giữa chính là "điểm gặp";
hoặc có đúng một đỉnh bậc $3$ , từ đó tỏa ra ba nhánh tới ba terminal.

  đường đi:   a ----- b ----- c        (điểm gặp = b)

  chữ Y:      a
               \
                m ----- c              (điểm gặp = m)
               /
              b

Cả hai trường hợp: có một đỉnh $m$ mà cây là hợp của ba đường $m \to a$ , $m \to b$ , $m \to c$ , mỗi đường dài ít nhất khoảng cách ngắn nhất. Ngược lại, hợp ba đường ngắn nhất từ bất kỳ $m$ nào là một đồ thị con liên thông chứa cả ba terminal. Vậy

$Steiner (a, b, c) = {min}_{m} (d_{a} [m] + d_{b} [m] + d_{c} [m]),$

với $d_{a}, d_{b}, d_{c}$ tính bằng $3$ lần BFS (không trọng số), 0-1 BFS hoặc Dijkstra. Tổng $O (n + m)$ hoặc $O (m \log n)$ . Công thức này đã được kiểm lại bằng DP bitmask ở trên trên $500$ đồ thị ngẫu nhiên có $3$ terminal.

Ba biến thể hay gặp:

Chi phí trên ô/đỉnh (xây đường trên ô): $d_{x} [m]$ đã tính ô $m$ ba lần, nên đáp án là ${min}_{m} (d_{a} [m] + d_{b} [m] + d_{c} [m] - 2 \cdot c o s t [m])$ .
Terminal là cả một vùng (một quốc gia gồm nhiều ô): tính $d_{x}$ bằng BFS đa nguồn từ mọi ô của vùng đó.
Trên cây, cây Steiner là duy nhất (hợp các đường đi), và có công thức đóng $\frac{d (a, b) + d (b, c) + d (c, a)}{2}$ : mỗi nhánh của chữ Y được đếm đúng hai lần trong tổng ba khoảng cách. Tổng quát cho $k$ đỉnh trên cây: sắp các đỉnh theo thời điểm vào DFS, cộng khoảng cách giữa các đỉnh liền kề theo vòng rồi chia $2$ (xem cây ảo và LCA).

Cây Steiner trong mặt phẳng Manhattan

Bài toán: cho $k$ điểm trên mặt phẳng, nối chúng bằng các đoạn ngang và dọc (dây điện chạy theo lưới phố, ống nước trên bản vẽ...) với tổng độ dài nhỏ nhất. Đây là cây Steiner với khoảng cách Manhattan (rectilinear Steiner tree). Điểm Steiner có thể nằm ở bất kỳ đâu, tức là vô hạn lựa chọn, nhưng có một định lý cứu ta:

Định lý Hanan. Luôn tồn tại một cây Steiner tối ưu chỉ gồm các đoạn nằm trên lưới Hanan: các đường ngang $y = y_{i}$ và các đường dọc $x = x_{i}$ đi qua các terminal.

Trực giác: nếu một đoạn ngang của cây không nằm trên đường $y = y_{i}$ nào, thì đẩy nó lên hoặc xuống một chút làm các đoạn dọc nối vào nó dài thêm ở một phía và ngắn đi ở phía kia; đẩy về phía có nhiều đoạn dọc hơn thì tổng không tăng, và cứ đẩy tới khi chạm một đường của lưới Hanan.

Lưới Hanan có tối đa $k \times k$ giao điểm và khoảng $2 k^{2}$ cạnh (trọng số là hiệu tọa độ giữa hai giao điểm kề nhau). Chạy thẳng DP $d p [mask] [v]$ trên đồ thị này: $O (3^{k} k^{2} + 2^{k} k^{2} \log k)$ , với $k \leq 10$ chỉ tốn vài mili giây. (Đã kiểm: kết quả trên lưới Hanan trùng kết quả trên toàn bộ lưới nguyên, $3000$ bộ ngẫu nhiên tới $5$ điểm.)

3 điểm: trung vị

Với $3$ điểm, cây Steiner Manhattan có độ dài đúng bằng nửa chu vi hình chữ nhật bao:

$L = (max x - min x) + (max y - min y) .$

Chặn dưới: hình chiếu của cây lên trục $x$ phải phủ đoạn $[min x, max x]$ , lên trục $y$ phải phủ $[min y, max y]$ . Đạt được bằng cách gặp nhau tại điểm $(x_{med}, y_{med})$ (trung vị theo từng trục): mỗi điểm đi thẳng tới đó theo hình chữ L, tổng $\sum | x_{i} - x_{med} | + \sum | y_{i} - y_{med} |$ và với ba số, tổng khoảng cách tới trung vị đúng bằng $max - min$ . Trên lưới ô vuông (đếm số ô thay vì độ dài), đáp án là $L + 1$ ô.

 ví dụ: A(0,0), B(4,1), C(2,3)     trung vị: x = 2, y = 1

 y
 3   .   .   C   .   .
             |
 2   .   .   |   .   .
             |
 1   .   .   +-------B            gặp nhau tại (2,1)
             |
 0   A-------+   .   .
     0   1   2   3   4    x

 độ dài = (4 - 0) + (3 - 0) = 7

4 điểm: có thể cần hai điểm Steiner

Từ $4$ điểm trở lên, nửa chu vi hình bao chỉ còn là chặn dưới. Ví dụ "chong chóng" $A (0, 1)$ , $B (1, 3)$ , $C (3, 0)$ , $D (4, 2)$ :

 y
 3   .   B   .   .   .
         |
 2   .   |   .   +---D
         |       |
 1   A---+-------+   .          điểm Steiner: (1,1) và (3,1)
                 |
 0   .   .   .   C   .
     0   1   2   3   4    x

Nửa chu vi hình bao: $4 + 3 = 7$ (không đạt được).
Cây Steiner tối ưu: $8$ , với hai điểm Steiner $(1, 1)$ và $(3, 1)$ , cả hai đều là giao điểm của lưới Hanan.
MST Manhattan trên $4$ điểm: $3 + 3 + 4 = 10$ .

Ngược lại, với dấu cộng $(0, 2), (2, 0), (2, 4), (4, 2)$ chỉ cần một điểm Steiner bậc $4$ ở tâm $(2, 2)$ : cây dài $8$ , còn MST dài $12$ . Đây là trường hợp xấu nhất cho MST trong mặt phẳng Manhattan (MST dài gấp $1, 5$ lần).

Cây Steiner Euclid (khoảng cách thường)

Khi dây nối được đi theo đường thẳng bất kỳ, lưới Hanan không còn đúng. Các tính chất cần nhớ:

Mỗi điểm Steiner có bậc đúng $3$ , ba đoạn tạo với nhau góc $120 °$ (nếu một góc nhỏ hơn, dời điểm đó sẽ rút ngắn cây). Có không quá $k - 2$ điểm Steiner.
3 điểm: điểm gặp là điểm Fermat của tam giác. Nếu tam giác có một góc $\geq 120 °$ thì điểm gặp chính là đỉnh đó; ngược lại là điểm nhìn ba cạnh dưới góc $120 °$ . Tam giác đều cạnh $1$ : MST dài $2$ , cây Steiner dài $\sqrt{3} \approx 1, 732$ .
4 điểm: cây tối ưu là MST, hoặc cây Fermat của $3$ điểm cộng một đoạn, hoặc cây "đầy đủ" với hai điểm Steiner ứng với một trong ba cách ghép cặp ${a, b} ∣ {c, d}$ , dựng bằng phép dựng Melzak (thay cặp $a, b$ bằng đỉnh tam giác đều dựng trên $a b$ ).
Với $k$ lớn hơn, tách cây tối ưu tại các terminal có bậc $\geq 2$ thành các "cây đầy đủ", rồi ghép bằng DP trên tập con giống hệt chuyển gộp ở trên.

Phần hình học Euclid khá nặng; hai đề VOI ở cuối trang là ví dụ trọn vẹn.

Độ phức tạp

Bước gộp: $O (3^{k} \cdot n)$ . Với mỗi mask và mỗi tập con của nó, ta duyệt $n$ đỉnh. Số cặp $(sub \subseteq mask)$ là $3^{k}$ : mỗi terminal có $3$ trạng thái "thuộc sub", "thuộc mask nhưng không thuộc sub", "không thuộc mask". Chỉ xét sub chứa bit thấp nhất giảm một nửa hằng số.
Bước lan: $O (2^{k} \cdot m \log m)$ . Mỗi mask chạy một lần Dijkstra đa nguồn trên toàn đồ thị.
Bộ nhớ: $O (2^{k} \cdot n)$ . Với $k = 10$ , $n = 10^{4}$ là khoảng $10^{7}$ giá trị: $80$ MB nếu dùng long long, $40$ MB nếu dùng int. Đây thường là giới hạn thật sự, không phải thời gian.
3 terminal: $3$ lần BFS/Dijkstra, $O (m \log n)$ (hoặc $O (n + m)$ khi không trọng số), bộ nhớ $O (n)$ .
Manhattan: $n = O (k^{2})$ , $m = O (k^{2})$ , nên $O (3^{k} k^{2})$ .

Giới hạn thực tế để nhận ra dạng bài: $k \leq 10$ đến $12$ terminal, $n$ từ vài trăm tới vài nghìn đỉnh (hoặc lưới cỡ $10 \times 10$ đến $100 \times 100$ ).

⚠️ Lỗi thường gặp

Dựng MST trên các terminal. Tính khoảng cách giữa các cặp terminal rồi chạy Kruskal cho kết quả lớn hơn đáp án khi cây tối ưu cần một đỉnh trung gian làm điểm rẽ nhánh (ví dụ chạy tay: $7$ thay vì $6$ ; hình sao: gần gấp đôi). MST chỉ là xấp xỉ.
Chỉ gộp mà không lan, hoặc lan trước khi gộp. Trong ví dụ chạy tay, $d p [{A, B}] [Y] = 5$ chỉ có được nhờ lan từ $X$ sau khi gộp. Thứ tự đúng với mỗi mask: gộp xong mới chạy Dijkstra. Chạy Dijkstra một lần duy nhất ở cuối cũng sai.
Dùng BFS thường cho bước lan dù cạnh không trọng số. Sau bước gộp, các đỉnh nguồn có giá trị ban đầu khác nhau, nên BFS đa nguồn đẩy tất cả vào hàng đợi cùng lúc sẽ sai. Phải dùng Dijkstra, hoặc hàng đợi theo "xô" (bucket) khi giá trị nhỏ.
Duyệt tập con sai biên. Vòng for (sub = (mask-1) & mask; sub > 0; ...) bỏ qua cả sub = mask và sub = 0. Nếu lỡ để sub = mask thì ta cộng thêm $d p [0] [v]$ : bằng $\infty$ gây tràn số, hoặc bằng $0$ thì vô hại nhưng thừa. Đừng quên kiểm tra < INF trước khi cộng.
Tràn số với INF. LLONG_MAX + x tràn thành số âm và thắng mọi phép min. Dùng INF = LLONG_MAX / 4 và chỉ cộng khi cả hai vế hữu hạn.
Đếm hai lần chi phí đỉnh. Trên lưới trọng số ô, gộp hai cây tại ô $v$ phải trừ $c o s t [v]$ ; công thức $3$ terminal phải trừ $2 \cdot c o s t [m]$ . Quên trừ thì đáp án lớn hơn đúng một vài ô, dễ tưởng là lệch do cách đếm (tính độ dài hay tính số ô) mà không nghĩ tới phép gộp.
Hết bộ nhớ. $2^{k} \cdot n$ tăng rất nhanh: $k = 12$ , $n = 10^{5}$ là $4 \cdot 10^{8}$ ô. Đọc kỹ giới hạn trước khi chọn DP bitmask; với $k = 3$ hãy dùng công thức điểm gặp.
Áp lưới Hanan cho khoảng cách Euclid. Lưới Hanan chỉ đúng với Manhattan. Với khoảng cách Chebyshev (đi $8$ hướng) thì xoay trục $u = x + y$ , $v = x - y$ để về Manhattan trước (độ dài nhân $2$ ).
Terminal không liên thông, hoặc $k \leq 1$ . Khi đồ thị không liên thông, mọi $d p [full] [v]$ là $\infty$ : in $- 1$ (hoặc theo đề). Khi $k = 1$ đáp án là $0$ ; hai terminal trùng đỉnh vẫn chạy đúng.

Biến thể / Mở rộng

Truy vết cây. Lưu với mỗi $(mask, v)$ nó đến từ phép gộp nào (sub) hay từ cạnh nào $(u \to v)$ , rồi đệ quy từ $(full, v^{*})$ để in các cạnh hoặc các ô được dùng.
Nhiều nhóm, mỗi nhóm phải liên thông nội bộ (Steiner forest). Tính $g [mask] = {min}_{v} d p [mask] [v]$ như trên, rồi làm thêm một DP trên các mask là hợp của nguyên nhóm: $h [mask] = min (g [mask], {min}_{sub} h [sub] + h [mask \oplus sub])$ , vì rừng tối ưu gồm các cây rời nhau.
Terminal là một vùng hay "chỉ cần chạm một trong nhiều đỉnh". Khởi tạo $d p [{i}] [v] = 0$ cho mọi $v$ thuộc vùng $i$ (tương đương thêm một đỉnh ảo nối với cả vùng bằng cạnh $0$ ).
$k$ lớn. Không còn lời giải chính xác nhanh; MST trên khoảng cách ngắn nhất giữa terminal là xấp xỉ trong phạm vi $2$ lần.
Cây Steiner trên cây. Duy nhất và tính được trực tiếp qua LCA; nhiều truy vấn thì dùng cây ảo, đếm/tối ưu trên mọi tập thì là DP trên cây hoặc knapsack trên cây.
Không nhầm với TSP. "Đi thăm hết $k$ điểm" (một hành trình) là DP bitmask kiểu TSP; "nối $k$ điểm bằng mạng" (cho phép rẽ nhánh) mới là cây Steiner. Hai bài có thể cùng dữ liệu lưới nhưng đáp án khác nhau.

Bài tập luyện

Luyện kỹ thuật

Pool CTOJ hiện chưa có bài ngoài VOI cần đúng DP $d p [mask] [v]$ với $k \geq 4$ ; các bài dưới đây luyện các trường hợp đặc biệt ( $3$ terminal, Manhattan, trên cây) của cây Steiner.

Cõng Bạn (piggyback) (Nghiệp dư) ba "terminal" $1$ , $2$ , $N$ với ba hệ số chi phí khác nhau: ba lần BFS rồi thử mọi điểm gặp $m$ , đúng công thức ${min}_{m} (B \cdot d_{1} [m] + E \cdot d_{2} [m] + P \cdot d_{N} [m])$ .
Nối ba ô đất (conthree) (Nâng cao) cây Steiner Manhattan của $3$ ô trên lưới, phải in ra các ô: đi qua hàng trung vị, đáp án $(max x - min x) + (max y - min y) + 1$ ô.
Ba đường đi trên cây (threepaths) (Kỳ cựu) chọn $3$ đỉnh để cây Steiner của chúng trên cây có nhiều cạnh nhất: dùng công thức $\frac{d (a, b) + d (b, c) + d (c, a)}{2}$ kết hợp đường kính.
Ba Quốc Gia (threest) (Kỳ cựu) cây Steiner $3$ terminal trên lưới, terminal là cả một vùng và chi phí trên ô: 0-1 BFS đa nguồn từ mỗi quốc gia, thử mọi ô gặp và trừ $2$ nếu ô gặp là ô ..
Kiểm soát hành tinh (maxctrl) (Kỳ cựu) tập đỉnh bị kiểm soát chính là cây Steiner của $S$ trên cây; nhận xét "mọi lá của cây Steiner là terminal" đưa bài về tìm cây con có ít lá và nhiều đỉnh nhất.

Đề VOI

Thiết kế đường điện (voi19_efill) (Chuyên gia) VOI 2019: phần dây dọc cạnh đa giác là cố định; phần dây ngầm là cây Steiner Euclid của $4$ điểm $a, b, c, d$ . Gợi ý: so sánh MST, cây Fermat của $3$ điểm cộng một đoạn, và cây hai điểm Steiner cho từng cách ghép cặp; luôn tính độ dài của cây dựng được thật.
Mạng truyền thông (voi21_comnet) (Kỳ cựu) VOI 2021: số kênh cần nâng cấp là số cạnh của cây Steiner của $k$ máy chủ trên cây. Cây Steiner ở đây chỉ là cách hiểu đề; phần chính là đếm số tập theo số cạnh bằng DP knapsack trên cây, phân loại theo đỉnh cao nhất của cây Steiner.
Cắm trại (voi26_camp) (Chuyên gia) VOI 2026: cây Steiner Euclid của $K \leq 10$ điểm trên đường tròn. Gợi ý: tính riêng các cây "đầy đủ" (mọi terminal là lá, điểm Steiner góc $120 °$ ) cho từng tập con, rồi ghép bằng DP trên tập con tách tại một terminal chung, đúng tinh thần chuyển gộp của $d p [mask] [v]$ .

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.