题目：有一个n*m的藏宝图，已经碎了，现在你有p个矩形，你知道p个矩形的左下角坐标x1,y1，右上角坐标x2,y2，让你从中选择最少的矩形重新构成这个藏宝图
思路：将p个矩形看成行，n*m个坐标看成列
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<list> #include<numeric> using namespace std; #define PI acos(-1.0) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f #define mm(a,b) memset(a,b,sizeof(a)) #define PP puts("*********************"); template<class T> T f_abs(T a){ return a > 0 ? a : -a; } template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; } template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} // 0x3f3f3f3f3f3f3f3f // 0x3f3f3f3f int limit;//重复覆盖时使用，行数选择的最大数目 struct DLX { const static int ROW = 1003, COL = 1003, SIZE = ROW * COL; int L[SIZE], R[SIZE], U[SIZE], D[SIZE]; //模拟指针 int col[SIZE], row[SIZE]; //所在列 所在行 int visn, visited[COL]; //用于估价函数 int sel[ROW], seln; //选择的行 int sz[COL]; //列元素数 int total/*节点编号*/, H[ROW]; void init(int clen) { //初始化列头指针 for(int i = 0; i <= clen; ++i) { L[i] = i - 1; R[i] = i + 1; U[i] = D[i] = i; sz[i] = 0; } for(int i=0;i<ROW;i++) H[i]=-1; for(int i=0;i<COL;i++) visited[i]=0; visn = 0; //用于重复覆盖的A*剪枝 L[0] = clen; R[clen] = 0; total = clen + 1; } void link(int r, int c) { U[total] = c; D[total] = D[c]; U[D[c]] = total; D[c] = total; if(H[r] < 0) H[r] = L[total] = R[total] = total; else { L[total] = H[r]; R[total] = R[H[r]]; L[R[H[r]]] = total; R[H[r]] = total; } sz[c]++; col[total] = c; row[total++] = r; } //-------------------- 精确覆盖 ------------------------- void remove(const int &c) { //删除c列上所有1元素所在的行 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], --sz[col[j]]; } void resume(const int &c) { //恢复c列上所有1元素所在的行 R[L[c]] = L[R[c]] = c; for(int i = U[c]; i != c; i = U[i]) for(int j = L[i]; j != i; j = L[j]) ++sz[col[U[D[j]] = D[U[j]] = j]]; } void dance(int now) { if(R[0] == 0) { if(seln==-1) seln=now; seln = min(seln,now); return; } int c=R[0], i, j; for(i = R[0]; i != 0; i = R[i]) //选择元素最少的列c if(sz[c] > sz[i]) c = i; remove(c); for(i = D[c]; i != c; i = D[i]) { //删除与c相连的行i for(j = R[i]; j != i; j = R[j]) //删除行元素所在的列j remove(col[j]); sel[now] = row[i]; //选择此行 保存行号 dance(now+1); for(j = L[i]; j != i; j = L[j]) resume(col[j]); } resume(c); } //-------------------- 重复覆盖 ------------------------- void _remove(const int &c) { for(int i = D[c]; i != c; i = D[i]) L[R[i]] = L[i], R[L[i]] = R[i]; } void _resume(const int &c) { for(int i = U[c]; i != c; i = U[i]) L[R[i]] = R[L[i]] = i; } int Astar(){ //估价函数 int res = 0; ++visn; for(int i = R[0]; i != 0; i = R[i]) { if(visited[i] != visn) { ++res; visited[i] = visn; for(int j = D[i]; j != i; j = D[j]) for(int k = R[j]; k != j; k = R[k]) visited[col[k]] = visn; } } return res; } bool _dance(int now) { if(now + Astar() > limit) return false; if(R[0] == 0) return now<=limit; int c=R[0], i, j; for(i = R[0]; i != 0; i = R[i]) //选择元素最少的列c if(sz[c] > sz[i]) c = i; for(i = D[c]; i != c; i = D[i]) { _remove(i); for(j = R[i]; j != i; j = R[j]) _remove(j); if(_dance(now + 1)) { //对于不同的题 这个地方常常需要改动 return true; } for(j = L[i]; j != i; j = L[j]) _resume(j); _resume(i); } return false; } }dl; int main(){ int T,n,m,p,x1,y1,x2,y2; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&p); dl.init(n*m); for(int r=1;r<=p;r++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); for(int i=x1+1;i<=x2;i++) for(int j=y1+1;j<=y2;j++){ int c=(i-1)*m+j; dl.link(r,c); } } dl.seln=-1; dl.dance(0); printf("%d\n",dl.seln); } return 0; }