HDU 4009 最小樹形圖：三維幾何與 Chu-Liu/Edmonds

題目

n 個村莊 (三維座標)，可選：自鑿井 (費用 = 高度×X) 或從有井村莊引水 (費用 = 曼哈頓距離×Y，若向高處流水額外 +Z)。求全村用水最小總費用，不可行輸出 "poor XiaoA"。n ≤ 1000。

建模為最小樹形圖

• 虛擬根節點 0，向每村莊 i 連邊，權 = z[i] * X (鑿井)。
• 村莊 i 可向 u 引水：邊 i→u，權 = manhattan(i,u)*Y + (z[u]>z[i]?Z:0)。
• 最小樹形圖根為 0，所有村莊必須可達 ⇔ 全村用水。

Zhuliu 算法同 POJ 3164

代碼結構相同，僅邊構建邏輯不同：

struct Node { int x,y,z; };
int manhattan(Node a, Node b) {
    return abs(a.x-b.x) + abs(a.y-b.y) + abs(a.z-b.z);
}
// 讀入後構建邊
for (i=1..n) edges.push_back({0, i, p[i].z * X});
for (i=1..n) for each u in list[i]:
    if (u!=i) {
        cost = manhattan(p[i], p[u]) * Y;
        if (p[u].z > p[i].z) cost += Z;
        edges.push_back({i, u, cost});
    }
ans = zhuliu(0, n+1, edges.size(), edges);
if (ans < 0) puts("poor XiaoA");
else printf("%d\n", ans);

複雜度

• 邊數 ≤ n + n² (最壞完全圖)，但實際輸入限制 m 較小。
• Zhuliu O(n·m) 在 n=1000 可接受。