HDU 題目：動態最小生成樹邊權修改查詢

問題描述

給定一張無向圖，包含 N 個點、M 條邊。有 K 條特殊邊，其權值會被放大。每給出一條特殊邊，需求出當前圖的最小生成樹（MST）權值。最終輸出這 K 次 MST 權值的平均值。

解題思路

1. 構建初始 MST：使用 Prim 算法求出原圖的 MST，記錄總權值 MinTreeValue，並建立 MST 的鄰接表 G。同時記錄每個節點在 MST 中的父節點 f[]。
2. 判斷邊類型：對於每條查詢邊 (u, v, c)：
   • 若該邊不在 MST 中（即 f[u] != v && f[v] != u），修改其權值不影響 MST，答案直接加上 MinTreeValue。
   • 若該邊在 MST 中，移除它會將 MST 分裂為兩個連通分量。需找到連接這兩個分量的最小非樹邊權值 best[u][v]，新 MST 權值為 MinTreeValue - dis[u][v] + min(best[u][v], c)。
3. 預處理 best[u][v]：
   • 定義 dp[root][u] 為從節點 u 到以 root 為根的子樹所有節點的最小非樹邊權值（即斷開 root 到其父節點的樹邊後，u 所在分量連接另一分量的最小代價）。
   • 通過兩次 DFS 計算：
     1. dfs1(u, fa, root)：自底向上，dp[root][u] = min( 子樹內的 dp, dis[root][u] )。
     2. dfs2(u, fa, root)：自頂向下，結合父節點方向的信息，得到斷開 (u, fa) 後連接兩分量的最小邊權 best[u][fa]。

核心代碼片段

// Prim 求 MST
ll prim() {
    memset(vis, 0, sizeof(vis));
    ll ans = 0;
    for (int i = 0; i < n; i++) { d[i] = dis[0][i]; f[i] = 0; G[i].clear(); }
    d[0] = INF; f[0] = -1; vis[0] = true;
    for (int i = 0; i < n - 1; i++) {
        int x = 0;
        for (int j = 1; j < n; j++) if (!vis[j] && d[j] < d[x]) x = j;
        vis[x] = true; ans += d[x];
        if (f[x] != -1) { G[x].push_back(f[x]); G[f[x]].push_back(x); }
        for (int j = 1; j < n; j++) if (!vis[j] && d[j] > dis[x][j]) { d[j] = dis[x][j]; f[j] = x; }
    }
    return ans;
}

// dfs1: 計算 dp[root][u]
int dfs1(int u, int fa, int root) {
    for (int v : G[u]) if (v != fa) dp[root][u] = min(dp[root][u], dfs1(v, u, root));
    if (fa != root) dp[root][u] = min(dp[root][u], dis[root][u]);
    return dp[root][u];
}

// dfs2: 計算 best[u][v]
int dfs2(int u, int fa, int root) {
    int ans = dp[u][root];
    for (int v : G[u]) if (v != fa) ans = min(ans, dfs2(v, u, root));
    return ans;
}

// 主流程
void solve() {
    memset(dp, 0x3f, sizeof(dp));
    ll MinTreeValue = prim();
    double ans = 0;
    for (int i = 0; i < n; i++) dfs1(i, -1, i);
    for (int i = 0; i < n; i++)
        for (int v : G[i]) best[i][v] = best[v][i] = dfs2(v, i, i);
    // 處理查詢...
}

複雜度分析

• Prim：O(N^2)（N ≤ 3000 可接受）。
• 兩次 DFS：每次 O(N^2)，總 O(N^2)。
• 查詢處理：O(1) 每條。
• 總體：O(N^2 + Q)，空間 O(N^2)。

關鍵點總結

本題核心在於「樹上邊替換」的經典模型：MST 中的樹邊被修改權值時，只需考慮用最小的非樹邊重新連接形成的兩個連通分量。通過以每個節點為根預處理 dp，巧妙地在 O(N^2) 內解決了所有樹邊的替換邊查詢，避免了每次查詢重新跑 MST 的高昂代價。