POJ 2263 Heavy Cargo：二分查找與並查集求最大載重路徑

POJ 2263 Heavy Cargo：二分查找與並查集求最大載重路徑

POJ 2263 要求在給定的圖中，找到從起點到終點的路徑，使得路徑上最小邊權（載重）最大。這是一個經典的「最大瓶頸路徑」問題，可用二分查找結合並查集高效求解。

問題建模

給定無向圖，每條邊有載重上限。貨車從城市 S 到 T，求可通過的最大載重。等價於：找最大的 W，使得只保留載重 ≥ W 的邊後，S 和 T 連通。

算法流程

1. 讀取所有邊，記錄最大載重 maxW。
2. 二分查找 W ∈ [0, maxW]。
3. 對於中間值 mid，初始化並查集，將所有載重 ≥ mid 的邊連接。
4. 若 S 和 T 連通，說明 mid 可行，向右搜索；否則向左搜索。
5. 最終 high 即為答案。

代碼實現要點

struct Edge { int u, v, w; } edges[20000];
int parent[300];

int find(int x) { return parent[x]==x ? x : parent[x]=find(parent[x]); }
void unite(int x, int y) { 
    int fx=find(x), fy=find(y); 
    if (fx!=fy) parent[fy]=fx; 
}

bool check(int mid, int n, int m, int s, int t) {
    for (int i=1; i<=n; i++) parent[i]=i;
    for (int i=0; i= mid) unite(edges[i].u, edges[i].v);
    return find(s) == find(t);
}

// 主函數中二分邏輯
int low=0, high=maxW, ans=0;
while (low <= high) {
    int mid = (low+high)>>1;
    if (check(mid, n, m, s, t)) {
        ans = mid; low = mid+1;
    } else high = mid-1;
}

複雜度分析

• 二分次數：O(log maxW)，maxW ≤ 10^6 時約 20 次。
• 每次檢查：O(m α(n))，α 為反阿克曼函數，視為常數。
• 總複雜度：O(m log maxW)，對 m=20000 極快。

優化提示

• 邊可預先按權值降序排序，並查集可增量添加，避免重複初始化（Kruskal 思想）。
• 使用路徑壓縮與按秩合並優化並查集。

此題展示了「二分答案 + 判定函數」的經典模式，並查集作為連通性判定工具，代碼簡潔高效。