HUST 1017 Exact Cover - DLX 算法求精確覆蓋

問題描述

給定 N×M 0-1 矩陣（N,M ≤ 1000），選擇若干行，使每一列恰好有一行被選中且該位置為 1。輸出任意一組解的行數及行索引，無解輸出 "NO"。

DLX 精確覆蓋算法

Dancing Links (DLX) 是 Knuth 提出的用於精確覆蓋問題的高效回溯算法。將矩陣稀疏表示為雙向十字鏈表，通過覆蓋/恢復列操作快速剪枝。

核心操作

• cover(c)：移除列 c 及所有包含 1 的行，更新鏈表。
• uncover(c)：逆操作恢復。
• 選擇列啟發式：選擇 1 最少的列（S[c] 最小），最小化分支因子。

代碼實現（C++）

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

    void init(int _n, int _m) { /* 初始化列頭 */ }
    void link(int r, int c) { /* 插入節點 */ }
    void remove(int c) { /* 覆蓋列 */ }
    void resume(int c) { /* 恢復列 */ }
    bool dance(int d) {
        if (R[0] == 0) { ansd = d; return true; }
        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]) {
            ans[d] = Row[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;
    }
};

int main() {
    int n, m;
    while (cin >> n >> m) {
        DLX solver;
        solver.init(n, m);
        for (int i = 1; i <= n; i++) {
            int cnt; cin >> cnt;
            while (cnt--) { int col; cin >> col; solver.link(i, col); }
        }
        if (!solver.dance(0)) cout << "NO\n";
        else {
            cout << solver.ansd;
            for (int i = 0; i < solver.ansd; i++) cout << ' ' << solver.ans[i];
            cout << '\n';
        }
    }
}

精確覆蓋 vs 可重複覆蓋

• 精確覆蓋：每列恰好覆蓋一次（本題、數獨、八皇后）。
• 可重複覆蓋：每列至少覆蓋一次（HDU 3335、HDU 5046），需修改 dance 邏輯允許重複選列。