您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1062 昂貴的聘禮：分層圖最短路 + 狀態壓縮等級限制

編輯：關於C++

POJ 1062 昂貴的聘禮詳解

題目：N (≤100) 個物品（1 號為酋長承諾）。每物品有價格 P、等級 L、若干替代品 (T, V)（用替代品 T 可減價 V）。等級差超過 M 的人不直接/間接交易。探險家無等級限制，但若與低等級交易，高等級者拒絕交易（視為間接接觸）。求得到 1 號物品的最小花費。

核心模型：分層圖 + 狀態為「允許的等級區間」

探險家最終與某等級區間 [L_low, L_high] 內的人交易（差 ≤ M）。因 1 號物品等級為 L₁，區間必包含 L₁，且長度 ≤ M。
枚舉區間下界 low = L₁-M .. L₁，上界 high = low + M。對每個區間，構建子圖：
- 只保留等級在 [low, high] 的物品。
- 邊：source -> i 代價 P_i（直接買）。
- 邊：T -> i 代價 V（用替代品換）。
對此子圖跑 最短路（SPFA/Dijkstra） 從 source 到 1 號。
全局最小值即答案。

為什麼這樣建模正確？

等級限制本質上要求所有參與交易的物品等級落在某長度 ≤ M 的區間內。
枚舉所有包含 L₁ 的長度 M 區間（共 M+1 個），覆蓋了所有合法交易集合。
在固定區間內，交易關係形成有向圖（替代品指向原物品），最短路即最小花費。

參考代碼 (C++)

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

const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };
int M, N;
int P[105], L[105];
vector> alt[105]; // 替代品 (T, V)

int solve_interval(int low, int high) {
    vector> g(N+2);
    int S = N+1;
    for (int i = 1; i <= N; ++i) {
        if (L[i] < low || L[i] > high) continue;
        g[S].push_back({i, P[i]}); // 直接買
        for (auto [t, v] : alt[i]) {
            if (L[t] >= low && L[t] <= high)
                g[t].push_back({i, v}); // 用替代品
        }
    }
    // SPFA
    vector dist(N+2, INF);
    vector inq(N+2, false);
    queue q;
    dist[S] = 0; q.push(S); inq[S] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (auto e : g[u]) {
            if (dist[e.to] > dist[u] + e.w) {
                dist[e.to] = dist[u] + e.w;
                if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; }
            }
        }
    }
    return dist[1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> M >> N) {
        for (int i = 1; i <= N; ++i) {
            int X; cin >> P[i] >> L[i] >> X;
            alt[i].clear();
            for (int j = 0; j < X; ++j) {
                int T, V; cin >> T >> V;
                alt[i].push_back({T, V});
            }
        }
        int ans = INF;
        for (int low = L[1] - M; low <= L[1]; ++low) {
            int high = low + M;
            ans = min(ans, solve_interval(low, high));
        }
        cout << ans << '\n';
    }
    return 0;
}