HDU 4081 秦始皇國道系統：最小生成樹與次小生成樹求最大比值

題目簡介

有 n 座城市，已知坐標和人口。需修路連通所有城市，使總花費最小（最小生成樹）。對 MST 上每條邊 (u,v)，考慮刪除它並用另一條邊 (x,y) 替換，使 (population[x]+population[y]) / (MST總權重 - w(u,v)) 最大。求該最大比值。

解題思路

1. 構建完全圖，邊權為歐氏距離，用 Prim 算法求 MST，記錄 MST 總權重 mst。
2. 在 MST 上以人口最多的城市為根 DFS，維護每棵子樹中人口最大的城市。
3. 枚舉 MST 上每條邊 (u,v)，刪除後分成兩棵子樹 T1, T2。最優替換邊必連接兩棵樹中人口最大的兩個城市。利用 DFS 信息快速查詢。
4. 計算比值 A/B，其中 A 為兩人口最大城市人口和，B 為 mst - w(u,v)。取最大值。

代碼框架

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1010;
struct Point { int x, y; } city[maxn];
int pop[maxn], n;
struct Edge { int u, v; double w; };
vector mstEdges;
double mstWeight;
int parent[maxn];
bool vis[maxn];
double ans = 0;

// Prim 求 MST
void prim() { ... }

// DFS 求子樹最大人口城市
int dfs(int u, int p) {
    int best = u;
    for (auto e : tree[u]) if (e.v != p) {
        int cand = dfs(e.v, u);
        if (pop[cand] > pop[best]) best = cand;
    }
    maxPop[u] = best;
    return best;
}

// 主程序枚舉 MST 邊計算最大比值
int main() {
    while (cin >> n) {
        // 讀入數據、構建完全圖、Prim、DFS、枚舉邊...
        printf("%.2f\n", ans);
    }
}

關鍵點

• 完全圖邊數 O(n^2)，Prim 用鄰接矩陣 O(n^2) 實現。
• DFS 從人口最大城市為根，遞歸記錄每個節點子樹內人口最大的城市。
• 枚舉 MST 邊時，替換邊的兩端點分別來自兩棵子樹的人口最大城市，保證 A 最大。