poj 2411 骨牌覆盖 dp
poj 3189 二分+多重匹配

zju 3209 学习dancing links

scturtle posted @ 2010年10月21日 04:10 in algorithm , 2144 阅读

用地图碎片完全覆盖大地图.每个地图碎片看作行,每个大地图里的格子看作一列,能覆盖则为1,然后DLX求精确覆盖.

#include <cstdio>
#include <cstring>
bool arr[601][1001];
#define MAX 0x3f3f3f3f
#define WID 1001
#define HGT 601
#define SIZE WID*(HGT+1)+10
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
    C[SIZE], Row[SIZE];//所在列 所在行
int S[WID + 10];
int sel[HGT],seln;//选择的列
int ans;

struct Dancer {
    int width, height;

    void init(int height,int width) {
        this->width = width;
        this->height = height;
        int p, x, y, last;
        for (x = 1; x <= width; x++) {//初始化列头指针
            L[x] = x - 1;
            R[x] = x + 1;
            U[x] = D[x] = x;
            S[x] = 0;//列元素
        }
        R[width] = 0;//0为总头指针
        p = width + 1;//每个节点编号
        for (y = 1; y <= height; y++) {//行
            last = R[0] = L[0] = 0;//作为每行虚拟头指针
            for (x = 1; x <= width; x++) {//列
                if (arr[y][x] != 0) {
                    U[p] = U[x];
                    C[p] = D[p] = x;
                    Row[p]=y;
                    L[p] = last;
                    S[x]++;
                    last = R[last] = U[x] = D[U[x]] = p++;
                }
            }
            R[last] = R[0];
            L[R[0]] = last;
        }
        L[0] = width;
        R[0] = 1;
        S[0] = MAX;
    }

    void remove(const int &c) {
        int i, j;
        L[R[c]] = L[c];//经典删除
        R[L[c]] = R[c];
        for (i = D[c]; i != c; i = D[i]) {
            for (j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --S[C[j]];
            }
        }
    }

    void resume(const int &c) {
        int i, j;
        for (i = U[c]; i != c; i = U[i]) {
            for (j = L[i]; j != i; j = L[j]) {
                ++S[C[j]];
                U[D[j]] = j;
                D[U[j]] = j;
            }
        }
        L[R[c]] = c;//经典恢复
        R[L[c]] = c;
    }

    bool dance() {
        if (R[0] == 0) return true;//空
        int c = 0, i, j;
        for (i = R[0]; i != 0; i = R[i])
            if (S[i] < S[c]) c = i;//元素最少的列
        remove(c);
        for (i = D[c]; i != c; i = D[i]) {//删除与c相连的行i
            sel[seln++]=Row[i];//选择此列 保存列号
            for (j = R[i]; j != i; j = R[j])//删除与i相连的列j
                remove(C[j]);
            //if (dance()) return true;
            if (dance()) {if(ans>seln) ans=seln;}
            for (j = L[i]; j != i; j = L[j])
                resume(C[j]);
            seln--;
        }
        resume(c);
        return false;
    }
};

#define get(x,y) m*x+y+1
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    Dancer dc;
    int n,m,c,i,j,k;
    int x1,y1,x2,y2;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d%d",&n,&m,&c);
        memset(arr,false,sizeof(arr));
        for(i=1;i<=c;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            for(j=x1;j<=x2-1;j++) for(k=y1;k<=y2-1;k++)
                arr[i][get(j,k)]=1;
        }
        ///////////////////
        seln=0;ans=MAX;
        dc.init(c,n*m);
        dc.dance();
        if(ans<MAX)
            printf("%d\n",ans);
        else printf("-1\n");
    }
}

nuaa 1507 http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1507

重复覆盖的代码

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
#define N 70
#define INF 0x3f3f3f3f

int L[N*N],R[N*N],U[N*N],D[N*N],Y[N*N],Sum[N];
int n,m;
int ans;
bool hash[N];

void remove(int c)
{
    int i;
    for(i = D[c]; i != c; i = D[i])
    {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}

void resume(int c)
{
    int i;
    for(i = U[c]; i != c; i = U[i])
    {
        L[R[i]] = i;
        R[L[i]] = i;
    }

}

int h()
{
    int c,i,j,ret = 0;
    memset(hash,0,sizeof(hash));
    for(c = R[0]; c != 0; c = R[c])
    {
        if(!hash[c])
        {
            ret++;
            hash[c] = true;
            for(i = D[c]; i != c; i = D[i])
                for(j = R[i]; j != i; j = R[j])
                    hash[Y[j]] = true;
        }
    }
    return ret;
}

void dfs(int dep)
{
    int idx,i,j,Min = INF;
    if(dep+h() >= ans) return;
    if(R[0] == 0) {ans = dep; return;}
    for(i = R[0]; i != 0; i = R[i])
    {
        if(Sum[i] < Min)
        {
            Min = Sum[i];
            idx = i;
        }
    }
    for(i = D[idx]; i != idx; i = D[i])
    {
        remove(i);
        for(j = R[i]; j != i; j = R[j])
            remove(j);
        dfs(dep+1);
        for(j = L[i]; j != i; j = L[j])
            resume(j);
        resume(i);
    }

}

int main()
{
    int i,j,k,num;
    int head,tail,cnt;
    scanf("%d%d",&m,&n);
    for(i = 0; i <= m; i++)
    {
        L[i] = i-1; R[i] = i+1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = m; R[m] = 0;
    cnt = m+1;
    for(i = 1; i <= n; i++)
    {
        head = tail = cnt;
        scanf("%d",&num);
        for(j = 1; j <= num; j++)
        {
            scanf("%d",&k);
            Sum[k]++;
            Y[cnt] = k;
            U[D[k]] = cnt;
            D[cnt] = D[k];
            U[cnt] = k;
            D[k] = cnt;
            L[cnt] = tail; R[tail] = cnt;
            R[cnt] = head; L[head] = cnt;
            tail = cnt; cnt++;
        }
    }
    ans = INF;
    dfs(0);
    if(ans == INF) ans = n;
    printf("%d\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter