Hướng dẫn cho Kết nối K đỉnh

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một cây gồm \(n\) đỉnh, mỗi đỉnh \(i\) có trọng số \(a_i\) và mỗi cạnh \(e\) có trọng số \(w_e\). Cần chọn ra một tập \(S\) gồm đúng \(k\) đỉnh sao cho giá trị sau đây là lớn nhất:

\[cost = \sum_{i \in S} a_i - \sum_{e \in E(S)} w_e\]

Trong đó \(E(S)\) là tập các cạnh của cây con nhỏ nhất chứa tất cả các đỉnh trong \(S\).

Phân tích

  • Đặc điểm của \(E(S)\): Cây con nhỏ nhất chứa tập các đỉnh \(S\) (thường gọi là Steiner Tree trên cây) sẽ bao gồm tất cả các đường đi giữa bất kỳ hai đỉnh nào trong \(S\).
  • Điều kiện một cạnh thuộc \(E(S)\): Một cạnh \(e\) chia cây ban đầu thành hai thành phần. Cạnh \(e\) thuộc \(E(S)\) khi và chỉ khi có ít nhất một đỉnh của \(S\) nằm ở thành phần bên này và ít nhất một đỉnh của \(S\) nằm ở thành phần bên kia.
  • Ngược lại: Cạnh \(e\) nối giữa đỉnh \(u\) và cha của nó \(p(u)\) không thuộc \(E(S)\) nếu:
    • Toàn bộ \(k\) đỉnh của \(S\) đều nằm trong cây con gốc \(u\).
    • Hoặc không có đỉnh nào của \(S\) nằm trong cây con gốc \(u\).
  • Bài toán: Đây là một bài toán quy hoạch động trên cây (Tree DP) kết hợp với kỹ thuật gộp túi (Knapsack-style DP on trees).

Cách làm đơn giản (Brute Force)

Ý tưởng

Với \(n \le 20\), ta có thể duyệt tất cả các tập con \(S\) có đúng \(k\) phần tử. Với mỗi tập \(S\), ta tìm cây con nhỏ nhất chứa \(S\) bằng cách sử dụng thuật toán tìm LCA hoặc đánh dấu các đường đi.

Độ phức tạp

  • Thời gian: \(O(2^n \cdot n)\) hoặc \(O(\binom{n}{k} \cdot n)\)
  • Đánh giá: Chỉ phù hợp với Subtask 1 (\(n \le 20\)).

Code Brute Force

C++
C++
#include <bits/stdc++.h>
using namespace std;

int n, k;
long long a[25];
vector<pair<int, int>> adj[25];
int parent[25], edge_w[25];

void dfs(int u, int p, int w) {
    parent[u] = p;
    edge_w[u] = w;
    for (auto& edge : adj[u]) {
        if (edge.first != p) dfs(edge.first, u, edge.second);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, 0, 0);
    long long max_cost = -2e18;
    vector<int> p(n);
    fill(p.end() - k, p.end(), 1);
    do {
        vector<int> S;
        long long current_a = 0;
        for (int i = 0; i < n; i++) {
            if (p[i]) {
                S.push_back(i + 1);
                current_a += a[i + 1];
            }
        }
        set<int> edges_in_E;
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                // Tìm đường đi giữa S[i] và S[j] (đơn giản hóa cho brute force)
                // Đánh dấu các đỉnh trên đường đi, cạnh nối u-p(u) thuộc E(S)
            }
        }
        // Tính tổng trọng số cạnh và cập nhật max_cost
    } while (next_permutation(p.begin(), p.end()));
    // Lưu ý: Code này chỉ mang tính minh họa ý tưởng duyệt.
    return 0;
}
Python
Python
# Ý tưởng tương tự: sử dụng itertools.combinations để duyệt tập S
import itertools

# Brute force cho n nhỏ bằng cách duyệt tổ hợp
# và tính Steiner Tree cho mỗi tổ hợp.

Hướng giải quyết (Tối ưu)

Quy hoạch động trên cây

Gọi \(dp[u][i]\) là giá trị lớn nhất khi chọn \(i\) đỉnh trong cây con gốc \(u\).
Tuy nhiên, để biết cạnh nối \(u\) với cha của nó có được tính vào \(E(S)\) hay không, ta cần biết có bao nhiêu đỉnh được chọn trong cây con gốc \(u\):

  • Nếu số đỉnh chọn trong cây con gốc \(u\) là \(x = 0\): Cạnh \((u, p(u))\) không thuộc \(E(S)\).
  • Nếu số đỉnh chọn trong cây con gốc \(u\) là \(x = k\): Cạnh \((u, p(u))\) không thuộc \(E(S)\) (vì tất cả \(k\) đỉnh đã nằm gọn trong cây con, không cần đi ra ngoài).
  • Nếu \(0 < x < k\): Cạnh \((u, p(u))\) chắc chắn thuộc \(E(S)\) vì có \(x\) đỉnh ở phía trong và \(k-x\) đỉnh ở phía ngoài.

Công thức chuyển trạng thái

Khi gộp cây con gốc \(v\) (con của \(u\)) vào \(u\):

  • Gọi \(dp[u][x]\) là giá trị tối ưu khi chọn \(x\) đỉnh từ các nhánh đã duyệt của \(u\).
  • Gọi \(dp[v][y]\) là giá trị tối ưu khi chọn \(y\) đỉnh từ cây con gốc \(v\).
  • Trạng thái mới: \(ndp[x+y] = \max(ndp[x+y], dp[u][x] + dp[v][y] - cost\_edge)\)
  • Trong đó \(cost\_edge = w(u, v)\) nếu \(0 < y < k\), ngược lại \(cost\_edge = 0\).

Chi tiết thực hiện

  1. Khởi tạo \(dp[u][0] = 0\) và \(dp[u][1] = a[u]\). Các giá trị khác bằng \(-\infty\).
  2. Duyệt các con \(v\) của \(u\), thực hiện gộp túi:
    \[ dp[u][x+y] = \max(dp[u][x] + dp[v][y] - (w(u, v) \text{ if } 0 < y < k \text{ else } 0)) \]
  3. Để thuật toán đạt độ phức tạp \(O(n^2)\), ta giới hạn vòng lặp \(x\) chạy đến kích thước hiện tại của cây con \(u\) và \(y\) chạy đến kích thước cây con \(v\). Đồng thời cả \(x, y\) đều không vượt quá \(k\).

Độ phức tạp

  • Thời gian: \(O(n \cdot k)\). Nhờ kỹ thuật gộp túi trên cây (Knapsack on trees), tổng độ phức tạp là \(O(n^2)\) hoặc \(O(nk)\) tùy theo cách giới hạn vòng lặp.
  • Bộ nhớ: \(O(nk)\) để lưu bảng DP.

Code tham khảo

C++
C++
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int n, k;
long long a[5005];
vector<pair<int, int>> adj[5005];
vector<long long> dp[5005];
int sub_size[5005];

void dfs(int u, int p) {
    sub_size[u] = 1;
    dp[u].assign(2, -INF);
    dp[u][0] = 0;
    dp[u][1] = a[u];

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == p) continue;

        dfs(v, u);

        int limit_u = min(k, sub_size[u]);
        int limit_v = min(k, sub_size[v]);
        vector<long long> next_dp(min(k, sub_size[u] + sub_size[v]) + 1, -INF);

        for (int x = 0; x <= limit_u; ++x) {
            if (dp[u][x] <= -INF) continue;
            for (int y = 0; y <= limit_v && x + y <= k; ++y) {
                if (dp[v][y] <= -INF) continue;

                // Cạnh (u, v) được tính nếu 0 < y < k
                long long edge_cost = (y > 0 && y < k) ? w : 0;
                next_dp[x + y] = max(next_dp[x + y], dp[u][x] + dp[v][y] - edge_cost);
            }
        }
        sub_size[u] += sub_size[v];
        dp[u] = next_dp;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(1, 0);
    cout << dp[1][k] << endl;

    return 0;
}
Python
Python
import sys

# Tăng giới hạn đệ quy cho cây sâu
sys.setrecursionlimit(10000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    ptr = 0
    n = int(input_data[ptr]); ptr += 1
    k = int(input_data[ptr]); ptr += 1

    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = int(input_data[ptr]); ptr += 1

    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(input_data[ptr]); ptr += 1
        v = int(input_data[ptr]); ptr += 1
        w = int(input_data[ptr]); ptr += 1
        adj[u].append((v, w))
        adj[v].append((u, w))

    inf = 10**18
    dp = [[] for _ in range(n + 1)]
    sub_size = [0] * (n + 1)

    def dfs(u, p):
        sub_size[u] = 1
        dp[u] = [-inf, a[u]]
        dp[u][0] = 0

        for v, w in adj[u]:
            if v == p:
                continue
            dfs(v, u)

            limit_u = min(k, sub_size[u])
            limit_v = min(k, sub_size[v])
            new_size = min(k, sub_size[u] + sub_size[v])
            next_dp = [-inf] * (new_size + 1)

            for x in range(limit_u + 1):
                if dp[u][x] <= -inf: continue
                for y in range(limit_v + 1):
                    if x + y > k: break
                    if dp[v][y] <= -inf: continue

                    edge_cost = w if (0 < y < k) else 0
                    val = dp[u][x] + dp[v][y] - edge_cost
                    if val > next_dp[x + y]:
                        next_dp[x + y] = val

            sub_size[u] += sub_size[v]
            dp[u] = next_dp

    dfs(1, 0)
    print(dp[1][k])

solve()

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.