HDU 3335 Divisibility - DLX 算法求最大反鏈（可重複覆蓋）

問題描述

給定 n 個正整數（n ≤ 1000），選擇盡可能多的數，使得任意兩個選中的數互不整除（即不存在一個能整除另一個）。輸出最大選擇數量。

建模為最大獨立集 / DLX 可重複覆蓋

構造二分圖：每個數為一個節點，若 a 整除 b 或 b 整除 a，連邊。問題轉化為求最大獨立集，即最小頂點覆蓋的補集。由 Kőnig 定理，二分圖最大獨立集 = 總頂點數 - 最大匹配數。但 n=1000，邊數可能達 O(n²)，用 Hopcroft-Karp 可行。本文採用 DLX（Dancing Links）求解最大團的補問題，實為求最大可重複覆蓋。

DLX 實現要點

• 構造 0-1 矩陣：行代表數，列代表數，若 i 整除 j 或 j 整除 i，矩陣[i][j]=1。
• DLX 求最大覆蓋：每次選擇列覆蓋最少行的列，遞歸搜索，剪枝使用啟發式函數 f() 估計上界。
• 由於矩陣對稱，可優化只考慮上三角。

核心代碼（C++）

struct DLX {
    static const int MAXN = 1005, MAXNODE = 1000000;
    int n, m, sz;
    int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE], Row[MAXNODE], Col[MAXNODE];
    int H[MAXN], S[MAXN], ansd;
    bool v[MAXN];

    void init(int _n, int _m) { /* 初始化列頭節點 */ }
    void link(int r, int c) { /* 插入節點 */ }
    void remove(int c) { /* 刪除列 */ }
    void resume(int c) { /* 恢復列 */ }
    int f() { /* 啟發式估計最大可選數 */ }
    void dance(int d) { /* 遞歸搜索最大覆蓋 */ }
};

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector a(n+1);
        for (int i=1;i<=n;i++) scanf("%lld", &a[i]);
        DLX solver;
        solver.init(n, n);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (a[i]%a[j]==0 || a[j]%a[i]==0)
                    solver.link(i, j);
        solver.ansd = 0;
        solver.dance(0);
        printf("%d\n", solver.ansd);
    }
}

複雜度與優化

DLX 在稀疏矩陣上極快，但稠密圖（如許多數互質）性能下降。實際比賽中常用二分圖最大匹配（Hopcroft-Karp O(E√V)）更穩定。本題數據範圍 DLX 可通過。