HDU 5046 Airport - 二分答案 + DLX 可重複覆蓋

問題描述

N 個城市（N ≤ 60），坐標 (x,y)，距離為曼哈頓距離。需在 K 個城市建機場，使每個城市到最近機場的最大距離最小。輸出該最小最大距離。

解法：二分距離 + DLX 判定可行性

1. 預計算所有城市對距離，存入數組並排序去重。
2. 二分答案：對於候選距離 D，構造覆蓋矩陣：若城市 i 到城市 j 距離 ≤ D，則 i 可覆蓋 j（即在 j 建機場可服務 i）。
3. 用 DLX 求是否能選 ≤ K 行覆蓋所有列（即所有城市被覆蓋）。DLX 的 dance 函數修改為判定是否存在深度 ≤ K 的覆蓋。
4. 二分找到最小可行 D。

DLX 判定邏輯

bool dance(int d) {
    if (d + f() > K) return false; // 剪枝：當前深度+啟發式上界 > K
    if (R[0] == 0) return d <= K;  // 全覆蓋且深度 ≤ K
    // 選擇列 S 最小的列
    int c = R[0];
    for (int i = R[0]; i; i = R[i]) if (S[i] < S[c]) c = i;
    remove(c);
    for (int i = D[c]; i != c; i = D[i]) {
        for (int j = R[i]; j != i; j = R[j]) remove(Col[j]);
        if (dance(d+1)) return true;
        for (int j = L[i]; j != i; j = L[j]) resume(Col[j]);
    }
    resume(c);
    return false;
}

完整流程

void solve() {
    sort(distances, distances+cnt);
    int l=0, r=cnt-1;
    while (l <= r) {
        int mid = (l+r)/2;
        dlx.init(n, n);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (d[i][j] <= distances[mid])
                    dlx.link(i, j);
        if (dlx.dance(0)) r = mid-1;
        else l = mid+1;
    }
    printf("Case #%d: %lld\n", caseNum++, distances[l]);
}

複雜度分析

距離數 ≤ 3600，二分 log(3600) ≈ 12 次。每次 DLX 在 n=60 圖上極快。總體輕鬆通過。