HDU 5046 Airport：二分 + DLX 重複覆蓋解機場選址

HDU 5046 Airport：二分 + DLX 重複覆蓋解機場選址

題目大意

給定 n 個機場坐標，需選出 K 個作為樞紐，使得每個機場到最近樞紐的曼哈頓距離最大值最小。n ≤ 60, K ≤ n。

解法框架

1. 二分答案：最大距離 D 的可行性單調。範圍 [0, 2e11]（坐標絕對值 ≤ 1e9）。
2. 可行性判定 → DLX 重複覆蓋：
   • 列：n 個機場（每個必須被覆蓋至少一次）。
   • 行：n 個機場作為樞紐的覆蓋範圍（第 i 行覆蓋所有與 i 距離 ≤ D 的機場）。
   • 目標：選 ≤ K 行覆蓋所有列。即經典「集合覆蓋」決策問題，用 Dancing Links (DLX) 解決。

DLX 關鍵結構

struct DLX {
    static const int MAXNODE = 4005; // n=60, n^2=3600 節點上限
    static const int MAXM = 65, MAXN = 65;
    int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];
    int row[MAXNODE], col[MAXNODE];
    int H[MAXN], S[MAXM]; // 行頭指針、列大小
    int ansd, ans[MAXN];  // 當前解深度、解記錄
    bool v[MAXNODE];      // 估價函數用訪問標記

    void init(int n, int m) { /* 初始化列頭雙向鏈表 */ }
    void Link(int r, int c) { /* 插入節點到第 r 行第 c 列 */ }
    void remove(int c), resume(int c); // 列刪除/恢復
    int f() { /* 估價：貪心計算覆蓋剩餘列所需最少行數 */ }
    bool Dance(int d) { /* 深度優先搜索，剪枝：d + f() > K */ }
};

核心剪枝：最小列啟發式 + 估價函數

• 選擇 S[c] 最小的列展開（最少選擇分支）。
• 估價函數 f()：貪心選擇覆蓋最多未覆蓋列的行，計算下界。若 d + f() > K 剪枝。

完整代碼框架

#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 65;
struct City { ll x, y; void read() { scanf("%lld%lld", &x, &y); } } c[N];
ll dist(City a, City b) { return llabs(a.x-b.x) + llabs(a.y-b.y); }

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, K; scanf("%d%d", &n, &K);
        for (int i = 1; i <= n; ++i) c[i].read();
        ll L = 0, R = 100000000000LL;
        while (L < R) {
            ll mid = (L + R) >> 1;
            DLX solver; solver.init(n, n);
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if (dist(c[i], c[j]) <= mid) solver.Link(i, j);
            if (solver.Dance(0)) R = mid;
            else L = mid + 1;
        }
        printf("Case #%d: %lld\n", cas, L);
    }
    return 0;
}

複雜度與技巧

• 二分 ~ log(2e11) ≈ 38 次。
• DLX 狀態空間極小（n≤60），配合強力剪枝極快。
• 曼哈頓距離計算用 llabs 防溢位。