其实是一道DLX的简单题， 可是我做了两天，虽然这两天做的很间断，但是我懂的了一些东西。
并不是你算法对的，感觉跟别人的代码差不多就可以达到和别人一样的效果， 这题算法大家都一样但是写出的程序速度却相差有10倍。 我就是因为写的烂，然后一直TLE，一开始我以为是哪里死循环了，后面一直TLE，看了别人的代码，然后一点一点的修改，最后才能过。。。
一定要注意自己代码的风格， 一些细节，能省就省，尤其是这种复杂度不定的搜索题， 更是要注意能省一点是一点!
Your boss once had got many copies of a treasure map. Unfortunately, all the copies are now broken to many rectangular pieces, and what make it worse, he has lost some of the pieces. Luckily, it is possible to figure out the position of each piece in the original map. Now the boss asks you, the talent programmer, to make a complete treasure map with these pieces. You need to make only one complete map and it is not necessary to use all the pieces. But remember, pieces are not allowed to overlap with each other (See sample 2).
Input
The first line of the input contains an integer T (T <= 500), indicating the number of cases.
For each case, the first line contains three integers n m p (1 <= n, m <= 30, 1 <= p <= 500), the width and the height of the map, and the number of pieces. Then p lines follow, each consists of four integers x1 y1 x2 y2 (0 <= x1 < x2 <= n, 0 <= y1 < y2 <= m), where (x1, y1) is the coordinate of the lower-left corner of the rectangular piece, and (x2, y2) is the coordinate of the upper-right corner in the original map.
Cases are separated by one blank line.
Output
If you can make a complete map with these pieces, output the least number of pieces you need to achieve this. If it is impossible to make one complete map, just output -1.
Sample Input
3 5 5 1 0 0 5 5 5 5 2 0 0 3 5 2 0 5 5 30 30 5 0 0 30 10 0 10 30 20 0 20 30 30 0 0 15 30 15 0 30 30
Sample Output
1 -1 2
Hint
For sample 1, the only piece is a complete map.
For sample 2, the two pieces may overlap with each other, so you can not make a complete treasure map.
For sample 3, you can make a map by either use the first 3 pieces or the last 2 pieces, and the latter approach one needs less pieces.
Author: HANG, Hang
Source: The 6th Zhejiang Provincial Collegiate Programming Contest
#include <stdio.h> #include <string.h> #define N 500005 #define INF 0x3ffffff int nn; int u[N],d[N],r[N],l[N],H[N]; int num[N]; int linkl[N]; int head; int n,m,p,size; int mi; int cnt; /*void build_matrix() { nn=n*m; // 1-n*m int i1,j,i,id,x1,y1,x2,y2; for(i1=1;i1<=p;i1++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); for(i=x1;i<x2;i++) for(j=y1;j<y2;j++) { id = i*m+j+1; // 只要编码的方式相同貌似就没有什么问题了 g[i1][id]=1; } } }*/ /*void build_link() { int id=0; r[id]=id; l[id]=id; u[id]=id; d[id]=id; int tmp=head; for(int i=1;i<=nn;i++) { ++id; r[tmp]=id; l[id]=tmp; l[0]=id; r[id]=0; tmp=id; } int tp=p; int tn=n; for(int i=1;i<=p;i++) { tmp=-1; int tmp1; for(int j=1;j<=nn;j++) { if(g[i][j]!=-1) { ++id; g[i][j]=id; if(tmp==-1) { tmp=id; tmp1=id; // 这个是第一个点 r[id]=id; l[id]=id; linkc[id]=i; linkl[id]=j; num[j]++; } else { r[tmp]=id; l[id]=tmp; l[tmp1]=id; r[id]=tmp1; tmp=id; linkc[id]=i; linkl[id]=j; num[j]++; } } } } ////////////////////// for(int i=1;i<=tn;i++) { tmp=i; u[i]=i; d[i]=i; for(int j=1;j<=tp;j++) { if(g[j][i]!=-1) { id=g[j][i]; d[tmp]=id; u[id]=tmp; u[i]=id; d[id]=i; tmp=id; } } } }*/ /*void build_link() { int c=nn; int r1=p; //列建立头(1 - c) ，顺便建立head = 0 for(int i=0;i<=nn;i++){ num[i]=0; d[i]=i; u[i]=i; r[i]=i+1; l[i]=i-1; } l[0]=nn,r[nn]=0; ///////////////////////////////// memset(H,-1,sizeof(H)); int cnt1 = c,id; for(int i=1;i<=r1;i++) for(int j=1;j<=c;j++) if(g[i][j]==1){ //link(i,j); num[j]++; id = ++cnt1; linkl[id] = j;//列 linkc[id] = i;//行 u[id] = u[j]; d[u[j]] = id; d[id] = j; u[j] = id; if(H[i]==-1){ H[i]=l[id]=r[id]=id; } else { l[id]=l[H[i]]; r[l[H[i]]]=id; r[id]=H[i]; l[H[i]]=id; } } }*/ void remove(int s) { l[r[s]]=l[s]; r[l[s]]=r[s]; for(int i=d[s];i!=s;i=d[i]) { for(int j=r[i];j!=i;j=r[j]) { u[d[j]]=u[j]; d[u[j]]=d[j]; num[linkl[j]]--; } } } void resume(int s) { l[r[s]]=s; r[l[s]]=s; for(int i=u[s];i!=s;i=u[i]) for(int j=l[i];j!=i;j=l[j]) { u[d[j]]=j; d[u[j]]=j; num[linkl[j]]++; } } void dfs(int s) { if(s+cnt>=mi) return ; if(r[head]==head) { if(s<mi) mi=s; return ; } int tmi=INF; int tu=head; for(int i=r[head];i!=head;i=r[i]) { if(num[i]<tmi) { tmi=num[i]; tu=i; } } remove(tu); cnt--; for(int i=d[tu];i!=tu;i=d[i]) { for(int j=r[i];j!=i;j=r[j]) { remove(linkl[j]); cnt--; } dfs(s+1); for(int j=l[i];j!=i;j=l[j]) { cnt++; resume(linkl[j]); } } cnt++; resume(tu); } void prepare(int tc,int tr) { for(int i=0;i<=tr;i++) { num[i]=0; u[i]=i; d[i]=i; r[i]=i+1; l[i+1]=i; } r[tr]=0; while(tc) H[tc--]=-1; } void link(int s,int c) { ++num[linkl[++size]=c]; d[size]=d[c]; u[d[c]]=size; u[size]=c; d[c]=size; // 头插入法 if(H[s]<0) H[s]=l[size]=r[size]=size; else { r[size]=r[H[s]]; l[r[H[s]]]=size; l[size]=H[s]; r[H[s]]=size; } } int main() { int i,j,k,x1,x2,y1,y2; int t; scanf("%d",&t); while(t--) { head=0; mi=INF; scanf("%d%d%d",&n,&m,&p); prepare(p,size=n*m); for(k=1;k<=p;k++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); for(i=x1;i<x2;++i) for(j=y1;j<y2;++j) link(k,i*m+j+1); } cnt=nn; //build_matrix(); //build_link(); dfs(0); if(mi==INF) printf("-1\n"); else printf("%d\n",mi); } return 0; }