HDU 3440 House Man（差分約束求最長路）

HDU 3440 House Man - 差分約束系統求最長路

這道題將「房子跳躍」問題建模為差分約束系統，通過求最長路來解決。

題目大意

有 n 棟房子，按高度從矮到高依次跳躍。相鄰跳躍的房子距離 ≤ d。求從第 1 棟跳到第 n 棟的最大總距離（或判斷無解）。

差分約束建模

設 x[i] 為到達第 i 棟房子（按高度排序後）的最大距離。約束條件：

• x[i] - x[i-1] ≤ d（相鄰高度房子距離限制）
• x[i] - x[i-1] ≥ 1 ⇔ x[i-1] - x[i] ≤ -1（必須嚴格遞增，至少跳 1）

轉化為圖的邊：

• i-1 → i 邊權 d
• i → i-1 邊權 -1

關鍵細節：原始編號與排序後編號映射

題目要求考慮原始 1 號和 n 號房子的相對位置。排序後，需記錄原始編號對應的排序位置，並在原始相鄰房子之間添加約束邊。

完整代碼實現（SPFA 求最長路）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int MAXN = 1010;
const int MAXM = 1000000;
const int INF = 0x3f3f3f3f;

struct House { int h, id; } p[MAXN];
struct Edge { int v, w, next; } e[MAXM];

int head[MAXN], dist[MAXN], inq[MAXN], outq[MAXN], pre[MAXN];
int n, h, D, T;

bool cmp(House a, House b) { return a.h < b.h; }

void addEdge(int u, int v, int w) {
    e[h] = {v, w, head[u]};
    head[u] = h++;
}

// SPFA 求最長路（檢測正環）
int spfa(int s) {
    for (int i = 0; i <= n; i++) dist[i] = -INF;
    memset(inq, 0, sizeof(inq));
    memset(outq, 0, sizeof(outq));
    
    queue q;
    q.push(s); inq[s] = 1; dist[s] = 0;
    
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        outq[u]++;
        if (outq[u] > n) return -1;  // 正環，無解
        
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (dist[v] < dist[u] + w) {  // 最長路：放寬條件
                dist[v] = dist[u] + w;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
    return 1;
}

int main() {
    int cases; scanf("%d", &cases);
    while (cases--) {
        memset(head, -1, sizeof(head)); h = 0;
        scanf("%d%d", &n, &D);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &p[i].h);
            p[i].id = i;
        }
        sort(p+1, p+n+1, cmp);
        
        // 排序後相鄰房子的距離約束
        for (int i = 2; i <= n; i++) {
            if (p[i-1].id < p[i].id) addEdge(i-1, i, D);
            else addEdge(i, i-1, D);
        }
        
        // 原始相鄰房子的嚴格遞增約束
        int pre_id[MAXN];
        for (int i = 1; i <= n; i++) pre_id[p[i].id] = i;
        for (int i = 2; i <= n; i++)
            addEdge(pre_id[i], pre_id[i-1], -1);
        
        int s = (p[1].id < p[n].id) ? 1 : n;
        int t = (p[1].id < p[n].id) ? n : 1;
        
        printf("Case %d: ", T++);
        if (spfa(s) == -1) printf("-1\n");
        else printf("%d\n", dist[t]);
    }
    return 0;
}

核心技術點總結

1. 差分約束 → 圖的最長路：x_j - x_i ≤ c ⇒ i → j 邊權 c
2. SPFA 求最長路：初始化 -INF，放寬條件為 dist[v] < dist[u] + w
3. 正環檢測：出隊次數 > n 說明有正環，約束衝突無解
4. 雙重約束建模：高度排序約束 + 原始編號相鄰約束

複雜度分析

• SPFA 平均 O(kE)，k 為平均鬆弛輪數
• N ≤ 1000，邊數約 3N，完全可行