Hướng giải của Hành Trình Thu Mua Nông Sản

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Hành trình qua \(N\) làng, bắt đầu ở \(0\), kết thúc ở bất kỳ

Tư duy

Với \(N \le 15\), số hoán vị \(N! \approx 10^{12}\) là quá lớn để duyệt trực tiếp. Ta dùng tập con để mô tả những làng đã ghé qua, kết hợp với vị trí hiện tại.

Thuật giải

Đặt dp[mask][v] = tổng chi phí nhỏ nhất để bắt đầu từ làng \(0\), đi qua đúng các làng trong mask (v phải thuộc mask), và kết thúc tại v.

  • Khởi tạo: dp[1 << 0][0] = 0 (chỉ có làng \(0\), đang ở \(0\), chi phí \(0\)).
  • Chuyển trạng thái: với mỗi mask đã biết, ta thử đến một làng v chưa ghé qua: cộng chi phí di chuyển từ u (cuối hành trình hiện tại) sang v.

Kết quả là min(dp[FULL][v]) với FULL = (1<<N) - 1 và v bất kỳ thuộc FULL.

Đánh giá độ phức tạp

  • Thời gian: \(O(N^2 \cdot 2^N)\).
  • Bộ nhớ: \(O(N \cdot 2^N)\).

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> c(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> c[i][j];

    int full = (1 << n) - 1;
    vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));
    dp[1][0] = 0;  // bắt đầu ở làng 0

    for (int mask = 1; mask <= full; mask++) {
        if (!(mask & 1)) continue;              // phải có bit làng 0
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;   // u phải thuộc mask
            if (dp[mask][u] >= INF) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;  // v chưa ghé
                int nmask = mask | (1 << v);
                dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + c[u][v]);
            }
        }
    }

    long long ans = INF;
    for (int v = 0; v < n; v++) ans = min(ans, dp[full][v]);
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.