POJ 3740 Easy Finding：DLX 算法解決精確覆蓋問題

問題描述

給定 M×N 的 0-1 矩陣（M ≤ 16, N ≤ 300），判斷是否存在若干行，使得每列在選中行中恰好有一個 1。多測試用例，輸出 "Yes, I found it" 或 "It is impossible"。

解題思路

經典精確覆蓋問題，直接套用 Dancing Links (DLX) 模板。注意：G++ 可能超時，建議用 C++ 編譯（GNU C++）或優化常數。

關鍵優化點

• 節點數上限：maxnode = 5000（M×N ≤ 4800）
• 列數上限：maxm = 310，行數上限：maxn = 18
• 使用啟發式策略：每次選擇節點數最少的列進行分支

完整代碼

#include <iostream>
#include <stdio.h>
using namespace std;

const int maxnode = 5000;
const int maxm = 310;
const int maxn = 18;

struct DLX {
    int n, m, size;
    int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode];
    int H[maxn], S[maxm];
    int ansd, ans[maxn];

    void init(int _n, int _m) {
        n = _n; m = _m;
        for (int i = 0; i <= m; ++i) {
            S[i] = 0; U[i] = D[i] = i;
            L[i] = i-1; R[i] = i+1;
        }
        R[m] = 0; L[0] = m;
        size = m;
        for (int i = 1; i <= n; ++i) H[i] = -1;
    }

    void link(int r, int c) {
        ++S[Col[++size] = c];
        Row[size] = r;
        D[size] = D[c]; U[D[c]] = size; U[size] = c; D[c] = size;
        if (H[r] < 0) H[r] = L[size] = R[size] = size;
        else {
            R[size] = R[H[r]]; L[R[H[r]]] = size;
            L[size] = H[r]; R[H[r]] = size;
        }
    }

    void remove(int c) {
        L[R[c]] = L[c]; R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j]; D[U[j]] = D[j]; --S[Col[j]];
            }
    }

    void resume(int c) {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                ++S[Col[U[D[j]] = D[U[j]] = j]];
        L[R[c]] = R[L[c]] = c;
    }

    bool dance(int d) {
        if (R[0] == 0) { ansd = d; return true; }
        int c = R[0];
        for (int i = R[0]; i != 0; 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;
    }
} x;

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        x.init(n, m);
        int num;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                cin >> num;
                if (num) x.link(i, j);
            }
        if (!x.dance(0)) printf("It is impossible\n");
        else printf("Yes, I found it\n");
    }
    return 0;
}

複雜度分析

• 時間：指數級最壞情況，但 DLX 剪枝極其有效，實際運行極快
• 空間：O(M×N) 節點存儲