zju 3209 学习dancing links
2010年10月21日 04:10
用地图碎片完全覆盖大地图.每个地图碎片看作行,每个大地图里的格子看作一列,能覆盖则为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; }