HDU 5148 Cities - 樹形 DP 選 k 點最小化期望距離

問題描述

樹上 n≤2000 點，選 k≤50 個點。從中等概率隨機選兩點，最小化它們距離的期望。輸出期望 × k²（即所有選點對距離和的最小值）。

DP 狀態與轉移

dp[u][j]：在以 u 為根的子樹中選 j 個點，子樹內兩兩距離和的最小值。合併子樹 v 時：

新增距離貢獻 = 邊長 w × (已選點數 in v) × (總選點數 k - 已選點數 in v) × 2？實際公式：

dp[u][j1+j2] = min(dp[u][j1+j2], dp[u][j1] + dp[v][j2] + w * j2 * (k - j2) * 2)。

原理：v 子樹內選 j2 點，其余 k-j2 點在 v 外。這 j2 點與外部 k-j2 點的距離必經邊 (u,v)，每對貢獻 w，共 j2*(k-j2) 對，雙向計算故 ×2。

代碼實現（C++）

#include 
using namespace std;
typedef long long LL;
const int N = 2010, M = 60;
LL dp[N][M], ans;
int head[N], tot;
struct Edge { int v, w, next; } e[N*2];

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

void update(LL &x, LL y) { if (y==-1) return; if (x==-1 || x>y) x=y; }

void dfs(int u, int fa) {
    dp[u][1] = 0;
    for (int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].v, w = e[i].w;
        if (v == fa) continue;
        dfs(v, u);
        for (int j1=k-1; j1>=1; j1--) {
            if (dp[u][j1]==-1) continue;
            for (int j2=1; j2k || dp[v][j2]==-1) break;
                update(dp[u][j1+j2], dp[u][j1] + dp[v][j2] + (LL)w * j2 * (k - j2) * 2);
            }
        }
    }
    update(ans, dp[u][k]);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k; scanf("%d%d", &n, &k);
        memset(head, -1, sizeof(head)); tot=0;
        for (int i=2;i<=n;i++) {
            int u,v,w; scanf("%d%d%d", &u,&v,&w);
            addEdge(u,v,w); addEdge(v,u,w);
        }
        memset(dp, -1, sizeof(dp)); ans=-1;
        dfs(1,0);
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點

• 背包式合併，j1 倒序防止重複使用當前子樹結果。
• 初始 dp[u][1]=0（單點無內部距離）。
• 全局 ans 取所有節點作為根時的 dp[u][k] 最小值。