用地图碎片完全覆盖大地图.每个地图碎片看作行,每个大地图里的格子看作一列,能覆盖则为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;
}