BZOJ 4070 [Apio2015] 雅加達摩天樓：分塊優化建圖 + Dijkstra 最短路

題目大意

N 個樓層，M 個電梯，每部電梯 (b, p) 表示從樓層 b 出發、步長 p 停靠（即 b, b+p, b+2p...）。從樓層 1 到樓層 N 最少乘坐次數。N ≤ 30000, M ≤ 200000。

核心難點：邊數爆炸

暴力建圖：每個電梯連接所有可達樓層，最壞 O(N²) 邊，Dijkstra 會 TLE。

分塊優化策略：√N 閾值

1. 大步長 (p > √N)：每部電梯可達樓層 ≤ √N，直接暴力連邊，總邊數 O(M√N)
2. 小步長 (p ≤ √N)：同模同餘類合併
   • 對每個 p，按 b % p 分組
   • 同組樓層形成等差數列，相鄰樓層連邊權重 1
   • 每組邊數 = 樓層數 - 1，總邊數 O(N√N)

關鍵代碼片段

大步長直接建邊

if (p > SQRT_N) {
    for (int k = b; k <= N; k += p) {
        for (int nxt = k + p; nxt <= N; nxt += p) {
            add_edge(k, nxt, (nxt - k) / p);  // 權重 = 步數
        }
    }
}

小步長分組建邊

// 預處理：按 (p, b%p) 分組
sort(elevators, elevators + M, [](a,b){ 
    return a.p != b.p ? a.p < b.p : a.mod < b.mod; 
});

for (int i = 0; i < M; ) {
    int j = i;
    while (j < M && same_group) j++;
    int p = elevators[i].p;
    vector floors;
    for (int k = i; k < j; k++) floors.push_back(elevators[k].b);
    sort(floors.begin(), floors.end());
    // 相鄰連邊
    for (int k = 1; k < floors.size(); k++) {
        add_edge(floors[k-1], floors[k], (floors[k] - floors[k-1]) / p);
    }
    i = j;
}

Dijkstra 模板

struct Node { int u; long long dist; };
bool operator<(Node a, Node b) { return a.dist > b.dist; } // 小頂堆

vector dist(N+1, INF);
priority_queue pq;
dist[1] = 0; pq.push({1, 0});

while (!pq.empty()) {
    auto [u, d] = pq.top(); pq.pop();
    if (d != dist[u]) continue;
    for (auto [v, w] : adj[u]) {
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.push({v, dist[v]});
        }
    }
}
cout << (dist[N] == INF ? -1 : dist[N]) << endl;

複雜度分析

• 大步長邊數：Σ (N/p)² ≈ N² Σ 1/p² = O(N√N) (p > √N)
• 小步長邊數：O(N√N) (每 p 最多 N 條邊，共 √N 個 p)
• 總邊數：O(N√N) ≈ 5×10⁶ (N=30000)
• Dijkstra：O(E log V) = O(N√N log N) ≈ 10⁸ 操作，可過

避坑指南

• INF = 0x3f3f3f3f 別漏寫 f (作者血淚教訓)
• 權重為 (目標-源)/p 而非固定 1
• 同組樓層需排序後相鄰連邊，保證最短路正確性
• 優先隊列用 pair<dist, node> 或自定義 struct 實現小頂堆

總結

本題展示了數學分塊優化圖建模的經典套路：

1. 識別參數範圍導致的複雜度懸殊 (大/小步長)
2. 大參數直接處理 (輸出敏感)
3. 小參數利用結構性質合併 (同模同餘類形成鏈)
4. 最終邊數從 O(N²) 降至 O(N√N)，配合 Dijkstra 完美通過