HDU 2489 Minimal Ratio Tree：暴力枚舉點集 + Prim 最小生成樹

題目大意

給定完全圖 n ≤ 15，每點有權 w[i]，每邊有權 map[i][j]。選擇恰好 m 個點構成子圖，在其上建立生成樹，使 (樹邊權和) / (所選點權和) 最小。輸出最優點集（編號遞增）。

解法：枚舉點集 + Prim 算最小生成樹

n ≤ 15 ⇒ 所有 m 元子集數 C(15, m) ≤ 6435，完全可行。
對每個候選點集：

1. 在誘導子圖上跑 Prim 算法求 MST 邊權和 sumE。
2. 計算比率 sumE / sumW，更新全局最優。

Prim 算法實現細節（針對子集）

• 用 vis[] 標記「已在 MST 中」與「不在候選集中」兩種狀態。原碼技巧：tmp[] 備份 vis[]，Prim 內部修改 vis[]，結束後 memcpy 還原。
• 起點任選集合內第一個點，dis[i] 初始化為到起點的邊權（非集合點設 INF）。
• 標準 O(n²) Prim，n=15 瞬時完成。

DFS 枚舉子集

void dfs(int pos, int cnt, double sumW) {
    if (cnt == m) {
        double sumE = prim();
        if (sumE / sumW < best) { best = sumE / sumW; memcpy(bestSet, vis, sizeof(vis)); }
        return;
    }
    for (int i = pos; i <= n; ++i) if (vis[i]) {
        vis[i] = 0; dfs(i, cnt+1, sumW + w[i]); vis[i] = 1;
    }
}

• vis[i]=1 表示「仍可選」，選中後設 0 並遞迴，回溯後恢復。
• pos 參數保證組合不重複、有序。

複雜度與優化

• 枚舉 C(15, m)，每次 Prim O(n²)=225，總操作 < 200 萬，極快。
• 可剪枝：若當前部分集合的理論下界已 ≥ 最優比率則剪枝（本題規模小無需）。

輸出格式

最優點集編號以空格分隔，行末無多餘空格。原碼用 flag 控制首個前不印空格。

總結

本題展示了「小規模圖上比率優化」的標準套路：枚舉分子（點集）→ 內層多項式算法求分母（MST）。n ≤ 15 使暴力枚舉成為最簡潔、最不易出錯的方案，無需分數規劃或參數搜尋等進階技巧。