Hướng dẫn cho Trạm gác trung tâm

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.

Subtask 1

Với subtask này, ta cần tìm cách để cho \(n\) đỉnh của đồ thị liên thông và tổng trọng số cạnh nhỏ nhất. Đây chính là bài toán tìm cây khung nhỏ nhất, có thể sử dụng thuật toán Kruskal hoặc Prim.

Độ phức tạp: \(O(N \times log{N})\).

Subtask 2

Nhận xét: Đồ thị kết nối \(k\) đỉnh đặc biệt sẽ là một đồ thị dạng cây gồm \(k\) đỉnh đặc biệt đó và một vài đỉnh phụ.

Ta tính trước đường đi ngắn nhất qua bất kì hai đỉnh bằng thuật toán Floyd-Warshall trong \(\mathcal{O}(N^3)\) và lưu vào mảng \(dist\).

Gọi \(dp_{mask, i}\) là tổng trọng số của cây kết nối tập \(mask\) đỉnh đặc biệt có gốc là đỉnh \(i\).

Với mỗi \(dp_{mask, i}\), ta cần duyệt qua tất cả các tập con của tập \(mask\), gọi là \(X\). Gọi \(Y = mask \setminus X\). Với cây con gốc \(i\) chứa tập \(X\) đỉnh đặc biệt và cây con gốc \(i\) chứa tập \(Y\) đỉnh đặc biệt, ta có thể gộp chúng lại thành cây con gốc \(i\) chứa tập \(mask\) đỉnh đặc biệt. Cập nhật \(dp_{mask, i} = min(dp_{X, i} + dp_{Y, i})\).

Duyệt qua \(n\) đỉnh. Xét đỉnh \(u\), nếu \(dp_{mask, u} < dp_{mask_i} + dist_{u, i}\), cập nhật lại \(dp_{mask, u} = dp_{mask_i} + dist_{u, i}\). (Ở đây ta lấy cây gốc \(i\) làm cây con gắn vào đỉnh \(u\) để tạo thành cây gốc \(u\)).

Độ phức tạp: \(O(N^3 + 3^N \times N + 2^N \times N^2)\)

Code tham khảo C++ (Sub 2)
C++
/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int maxk = 10;
const int maxn = 2e2 + 5;
const int oo = 1e18;

int dp[(1 << 10) + 1][maxn];
int a[maxn];
int d[maxn][maxn];

int n, m, k;

void floyd(){
    for (int k = 1; k <= n; k++){
        for (int u = 1; u <= n; u++){
            for (int v = 1; v <= n; v++){
                if (d[u][v] > d[u][k] + d[k][v]){
                    d[u][v] = d[u][k] + d[k][v];
                }
            }
        }
    }
}



void PROGRAM(int _){
    cin >> n >> m >> k;

    assert(k <= 10);

    for (int i = 0; i < k; i++) cin >> a[i];

    for (int u = 1; u <= n; u++){
        for (int v = u + 1; v <= n; v++){
            d[u][v] = d[v][u] = oo;
        }
    }

    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }

    floyd();

    for (int mask = 0; mask < (1 << k); mask++){
        for (int u = 1; u <= n; u++) dp[mask][u] = oo;
    }

    for (int i = 0; i < k; i++){
        for (int u = 1; u <= n; u++){
            dp[(1 << i)][u] = d[a[i]][u];
        }
    }

    int ans = oo;

    for (int mask = 1; mask < (1 << k); mask++){
        if (__builtin_popcount(mask) == 1) continue;
        for (int i = 1; i <= n; i++){
            for (int mask1 = mask; mask1; mask1 = (mask1 - 1) & mask){
                int mask2 = mask ^ mask1;
                if (!mask1 || !mask2) continue;
                dp[mask][i] = min(dp[mask][i], dp[mask1][i] + dp[mask2][i]);
            }
            for (int u = 1; u <= n; u++){
                dp[mask][u] = min(dp[mask][u], dp[mask][i] + d[u][i]);
            }
        }
    }

    for (int i = 1; i <= n; i++) ans = min(ans, dp[(1 << k) - 1][i]);

    cout << ans << endl;

}

signed main(){
    freopen("TG.INP", "r", stdin);
    freopen("TG.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

Bình luận

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