POJ 2253 Frogger 詳解：最小生成樹變體求最小最大邊權路徑

題目大意

青蛙從石頭 1 跳到石頭 2，每次跳躍距離為兩石頭間歐氏距離。求路徑中最長單次跳躍距離最小的值（即「最小化最大邊權路徑」）。

核心洞察：最小生成樹性質

在無向圖中，任意兩點間的最小最大邊權路徑，其最大邊權等於最小生成樹 (MST) 上該兩點路徑的最大邊權。證明：MST 的任意兩點路徑為所有路徑中字典序最小的邊權序列（瓶頸最短路性質）。

算法流程

1. 計算所有石頭對距離，構建完全圖邊集
2. Kruskal 算法構建 MST：
   • 邊按權值升序排序
   • 並查集合併，共 n-1 條邊入樹
3. 在 MST 上從節點 1 DFS/BFS 到節點 2，記錄路徑上最大邊權

關鍵代碼片段

struct Edge {
    int u, v;
    double w;
    bool operator<(const Edge& other) const { return w < other.w; }
};

vector edges;
vector> mst[MAXN];  // MST 鄰接表
int parent[MAXN];

int find(int x) { return parent[x]==x ? x : parent[x]=find(parent[x]); }

void kruskal(int n) {
    sort(edges.begin(), edges.end());
    for (int i=1; i<=n; ++i) parent[i]=i;
    int cnt = 0;
    for (auto& e : edges) {
        int fu=find(e.u), fv=find(e.v);
        if (fu != fv) {
            parent[fu] = fv;
            mst[e.u].push_back({e.v, e.w});
            mst[e.v].push_back({e.u, e.w});
            if (++cnt == n-1) break;
        }
    }
}

double dfs(int u, int target, int fa, double curMax) {
    if (u == target) return curMax;
    for (auto [v, w] : mst[u]) {
        if (v != fa) {
            double ans = dfs(v, target, u, max(curMax, w));
            if (ans >= 0) return ans;
        }
    }
    return -1;
}

複雜度分析

• 邊生成：O(n²) — 完全圖 n≤200 可接受
• 排序：O(n² log n)
• Kruskal：O(n² α(n))
• DFS：O(n)
• 總體：O(n² log n) 時間，O(n²) 空間

優化方向

1. Prim 算法 + 優先隊列：O(n²) 無需顯式生成所有邊，適合稠密圖
2. 二分答案 + 連通性檢查：二分最大跳躍距離，檢查 1 和 2 是否連通（Union-Find 或 BFS），O(n² log 精度)
3. 直接修改 Dijkstra：dist[v] = min(dist[v], max(dist[u], w(u,v)))，O(n²) 求 1 到所有點的最小最大邊權

關鍵點總結

1. 「最小化路徑最大邊權」= MST 上路徑最大邊權（瓶頸最短路）
2. Kruskal 構建 MST 後，樹上任意兩點路徑唯一，DFS 即可
3. 雙精度輸出格式：printf("%.3f\n\n", ans) 注意雙換行
4. 多測試用例，n=0 結束

總結

POJ 2253 是 MST 瓶頸路徑性質的直接應用。理解「MST 上任意兩點路徑為所有路徑中最大邊權最小」是解決此類問題的關鍵。對於 n≤200 的完全圖，Kruskal 代碼簡潔；大規模稠密圖首選 Prim 優化版或修改版 Dijkstra。