zoj 3209.Treasure Map（DLX精确覆盖）

时间：2022-01-28 16:34:38

直接精确覆盖

开始逐行添加超时了，换成了单点添加

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

#define FOR(i,A,s)  for(int i = A[s]; i != s; i = A[i])

#define exp 1e-8

const int MAX = ;

int n, m, k, t, len;

struct DLX {

    int n, Size;//Size为尾指针，真正大小

    int row[MAX], col[MAX];//记录每个点的行列

    int U[MAX], D[MAX], R[MAX], L[MAX]; //4个链表

    int S[MAX],H[MAX];//每列1的个数

    int ncnt, ans[MAX];

    void init (int n) {

        this->n = n;

        ncnt = MAX;

        //增加n+1个辅助链表，从0到n

        for (int i = ; i <= n; i++)

            U[i] = D[i] = i, L[i] = i - , R[i] = i + ,S[i]=;

        R[n] = , L[] = n; //头尾相接

        Size = n + ;

        memset (H, -, sizeof H);

    }

    //单点添加

    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] < ) 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 (i, D, c)

        FOR (j, R, i)

        U[D[j]] = U[j], D[U[j]] = D[j], --S[col[j]];

//        //重复覆盖

//        for (int i = D[c]; i != c; i = D[i])

//            L[R[i]] = L[i], R[L[i]] = R[i];

    }

    void Restore (int c) {

        FOR (i, U, c)

        FOR (j, L, i)

        ++S[col[j]], U[D[j]] = j, D[U[j]] = j;

        L[R[c]] = c, R[L[c]] = c;

        //重复覆盖

//        for (int i = U[c]; i != c; i = U[i])

//            L[R[i]] = R[L[i]] = i;

    }

    bool v[MAX];

    int ff() {

        int ret = ;

        for (int c = R[]; c != ; c = R[c]) v[c] = true;

        for (int c = R[]; c != ; c = R[c])

            if (v[c])

            {

                ret++;

                v[c] = false;

                for (int i = D[c]; i != c; i = D[i])

                    for (int j = R[i]; j != i; j = R[j])

                        v[col[j]] = false;

            }

        return ret;

    }

    bool dfs (int d) {

        if (d >= ncnt) return ;

        //if (d + ff() > k) return 0;//重复覆盖

        if (R[] == ) {

            ncnt = min (ncnt, d);

            return ;

        }

        int c = R[];

        for (int i = R[]; i != ; i = R[i])

            if (S[i] < S[c])

                c = i;

        Remove (c);//精确覆盖

        FOR (i, D, c) {

            //Remove (i);//重复覆盖

            ans[d] = row[i];

            FOR (j, R, i) Remove (col[j]);//精确覆盖

            //FOR (j, R, i) Remove (j);//重复覆盖

            //if (dfs (d + 1) ) return 1;

            dfs (d + );

            FOR (j, L, i) Restore (col[j]);//精确覆盖

            //FOR (j, L, i) Restore (j);//重复覆盖

            //Restore (i);//重复覆盖

        }

        Restore (c);//精确覆盖

        return ;

    }

    bool solve (vector<int> &v) {

        v.clear();

        if (!dfs () ) return ;

        for (int i = ; i < ncnt; i++) v.push_back (ans[i]);

        return ;

    }

} Dance;

int columns[][ * ];

int main() {

    scanf ("%d", &t);

    while (t--) {

        memset (columns, , sizeof columns);

        scanf ("%d %d %d", &n, &m, &k);

        len = n * m;

        Dance.init (len);

        int x,y,xx,yy;

        for (int p = ; p <= k; p++) {

            scanf ("%d %d %d %d", &x, &y, &xx, &yy);

            for (int i = x+; i <= xx; i++)

                for (int j = y+; j <= yy; j++)

                    Dance.Link (p, j + (i-)*m);

        }

        Dance.dfs ();

        printf ("%d\n", Dance.ncnt == MAX ? - : Dance.ncnt);

    }

    return ;

}

相关文章