HDU 4756 Install Air Conditioning：次小生成樹 (MST + 非樹邊替換 + LCA 最大/次大邊)

問題描述

N 個宿舍 + 1 個電廠 (共 n ≤ 1000 點)，已知坐標。邊權 = 歐氏距離 × 單價 k。需在保證所有點連通且去掉任意一條邊後仍連通 (即圖為 2-邊連通) 的前提下，求最小總成本。輸出保留兩位小數。

關鍵轉化：次小生成樹

「去掉一條邊仍連通」等價於尋找 次小生成樹 (Second Best MST)：在所有生成樹中，權值嚴格大於 MST 且最小的樹。若 MST 唯一，次小生成樹可通過「替換 MST 上一條邊」得到。

算法流程 (Prim + DFS/LCA)

1. Prim 求 MST，記錄樹邊 (vis[u][v]=1)、總權 mstSum、構建樹鄰接表。
2. 預處理 LCA：對樹上任意兩點，求路徑上 最大邊 與 次大邊 (嚴格小於最大)。用倍增或 DFS + 線段樹均可，n=1000 時 O(n²) 預處理亦可接受。
3. 枚舉非樹邊 (u,v)：加入形成環，需刪除環上一條樹邊。為使新樹權值最小且 > MST，應刪除環上 最大邊；若該非樹邊權重等於最大邊，則刪除 次大邊 (避免得到相同 MST)。
4. 候選答案 = mstSum - maxEdge + w(u,v) (或 - secondMax + w)，取最小值。

核心代碼片段 (DFS 版 LCA 預處理)

const int MAXN = 1005;
double dis[MAXN][MAXN], dp[MAXN][MAXN]; // dp[u][v] = u-v 路徑上次大邊
bool inMST[MAXN][MAXN];
double mstSum;

void dfs(int root, int u, int fa) { // 以 root 為起點，更新 root 到各子樹的最短非樹邊
    double best = INF;
    for (int e = head[u]; ~e; e = nxt[e]) {
        int v = to[e];
        if (v == fa) continue;
        double tmp = dfs(root, v, u);
        best = min(best, tmp);
        dp[u][v] = dp[v][u] = min(dp[u][v], best);
    }
    if (root != fa) best = min(best, dis[root][u]); // 非樹邊 (root,u)
    return best;
}

// 主程序
Prim(); // 得到 mstSum, inMST
for (int i=1;i<=n;i++) dfs(i, i, -1); // 預處理 dp
double ans = mstSum;
for (int u=2; u<=n; ++u)
    for (int v=2; v

注意點

  
題目實際詢問：「在最小策略前提下，最多花費多少」 → 即次小生成樹權值 (因不知道哪條邊會被禁止，需準備次優方案)。
  
三點不共線、坐標唯一，保證邊權唯一，MST 唯一，簡化次大邊判斷。
  
雙精度輸出 %.2lf，乘以單價 k。