HDU 4435 Charge Station：暴力枚舉 + 圖連通性判斷求最小建站成本

HDU 4435 Charge Station：最小油站建設成本（二進制權值 + 圖連通性）

題目大意

N (≤128) 座城市，城市 1 有宮殿。車滿油可行駛 D 米。城市間距離 = 坐標歐氏距離向上取整。在城市建油站成本為 2^(i-1)（城市 i）。城市 1 必須建油站。求能讓車從 1 出發遍歷所有城市並返回 1 的最小總成本，輸出二進制表示。若全建也無法遍歷，輸出 -1。

核心觀察：二進制權值的貪心性質

成本為 2 的冪次，二進制下互不相同位。總成本最高位為 0 的方案必然更小。因此：

• 從最高位（城市 N）向最低位嘗試刪除油站
• 刪除後若圖仍連通（滿足行駛條件），則確定不建該站
• 否則必須保留

這是經典的「按位貪心 + 可行性檢查」模式。

可行性檢查：圖連通性 + 行駛約束

建立圖：城市間距離 ≤ D 則有邊。油站城市可作為「充電點」，車可在油站間行駛距離 ≤ D 的路徑。

判斷條件（BFS/DFS/並查集）：

1. 所有油站城市必須連通（構成連通塊）
2. 非油站城市到最近油站的距離 × 2 ≤ D（來回不超過續航）

完整演算法流程

1. 讀入城市坐標，預計算距離矩陣 dist[i][j] = ceil(歐氏距離)
2. 初始全部建站 vis[i] = true
3. 若全建站仍不滿足條件 → 輸出 -1
4. for i = N down to 1:
       vis[i] = false  // 嘗試不建
       if (!check()) vis[i] = true  // 不行則恢復
5. 找最高位保留的油站，輸出二進制串

check() 函數實現（BFS 版）

bool check() {
    // dis[i]: 非油站城市 i 到最近油站的最短距離
    // 初始：油站城市 dis=0 入隊，非油站 dis=INF
    queue q;
    q.push(1);  // 城市 1 必為油站
    vis[1] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 1; v <= n; ++v) {
            if (dist[u][v] > D) continue;  // 超過續航
            if (vis[v]) continue;
            // 更新距離
            if (isStation[v]) {
                q.push(v);  // 油站可繼續擴展
            }
        }
    }
    // 檢查：所有油站是否連通？所有非油站 2*dis ≤ D？
}

複雜度分析

• 距離矩陣：O(N²)
• 每次 check：O(N²) BFS
• 嘗試 N 次：O(N³) ≈ 128³ ≈ 2×10⁶，完全可行

樣例解析

Case 1: 3 城市, D=3
座標: (0,0) (0,3) (0,1)
距離: 1-2=3, 1-3=1, 2-3=2
最優：建站 1,2 → 成本 2^0+2^1=3 → 二進制 11

核心收穫

1. 2 的冪次成本 → 按位從高到低貪心刪除
2. 可行性檢查 = 圖連通性 + 幾何約束（來回距離）
3. 輸出二進制無前導零：找最高位 1 向下輸出
4. 並查集可替代 BFS 加速連通性判斷