HDU 4085 Peach Blossom Spring：斯坦納樹 + 狀態壓縮 DP + 記憶化搜索

題目大意

n 個點、m 條可建邊（帶權）、k 個人。初始第 1..k 點各一人，目標移動到第 n-k+1..n 點（各點一人）。從給定邊中選擇構建，使總花費最小，且所有人能到達目標點（允許多條不連通路徑）。

解題思路

核心模型：斯坦納樹的變體。需連接 2k 個特殊點（起點集 S、終點集 T），但不要求全部連通——只需每個起點與某個終點連通，且起點與終點一一對應（隱含於狀態壓縮中）。

步驟 1：Floyd 求全源最短路

先跑 Floyd 將圖轉為完全圖，邊權為最短路徑長度。

步驟 2：狀態壓縮 DP 計算 dp[u][mask]

• mask 共 2k 位，低 k 位表示起點集，高 k 位表示終點集。
• dp[u][mask]：以 u 為根，連接 mask 中所有特殊點的最小花費。
• 初始化：dp[u][1<<i] = dist[u][special[i]]。
• 子集轉移：dp[u][mask] = min(dp[u][sub] + dp[u][mask^sub])，枚舉 sub ⊂ mask。
• Dijkstra/SPFA 松弛：對固定 mask，將 dp[*][mask] 作為源點跑最短路，更新 dp[v][mask] = min(dp[v][mask], dp[u][mask] + dist[u][v])。

步驟 3：記憶化搜索組合答案

合法狀態 mask 需滿足：popcount(low k bits) == popcount(high k bits)（人數等於目標點數）。

solve(mask) = min_u dp[u][mask]，若 mask 可拆分為兩個獨立連通塊 mask1, mask2，則 solve(mask) = min(solve(mask1) + solve(mask2))。遞歸枚舉子集 sub = (sub-1) & mask。

最終答案 solve((1<<2k)-1)。若為 INF 輸出 No solution。

複雜度

• Floyd：O(n³)，n ≤ 50 可行。
• 狀態數 2^(2k) ≤ 2^10 = 1024（k ≤ 5）。
• DP：O(n * 3^(2k) + 2^(2k) * n²)，實際極快。

參考代碼框架 (C++ 關鍵部分)

const int INF = 1e8;
int n, m, k, special[10];
int dist[55][55], dp[55][1<<10];
int memo[1<<10];

int check(int mask) { // 檢查合法性並返回單連通塊最小值
    int a=0, b=0;
    for (int i=0;i