ZOJ-3209 dancinglink模板题
zjhl2
posted @ 2015年12月14日 01:27
with tags
dancinglink ZOJ
, 344 阅读
题意:用p(500)个矩形(给出左下角和右上角)拼成一个n×m(30×30)的大矩形,输出最少使用个数。
把n×m每个格子都看成交叉十字循环双向链的一列,于是有n×m列,每个矩形都覆盖了一些列,于是就转化成01矩阵的精确覆盖,直接上模板。
建图的时候注意细节
#include<cstdio> const int N=505005,INF=0x3f3f3f3f; struct DLX { int L[N],R[N],U[N],D[N],row[N],col[N]; int H[505]; int ansd,ans[505]; int s[1005]; int tot,n,m; void init(int _n,int _m) { n=_n; m=_m; tot=m; for (int i=0;i<=m;i++) L[i]=i-1,R[i]=i+1,U[i]=i,D[i]=i,s[i]=0; L[0]=m; R[m]=0; for (int i=1;i<=n;i++) H[i]=-1; } void link(int i,int j) { s[j]++; ++tot; row[tot]=i; col[tot]=j; U[tot]=U[j]; D[tot]=j; D[U[j]]=tot; U[j]=tot; if (H[i]<0) { H[i]=tot; L[tot]=tot; R[tot]=tot; } else { L[tot]=L[H[i]]; R[tot]=H[i]; R[L[H[i]]]=tot; L[H[i]]=tot; } } void remove(int c) { R[L[c]]=R[c]; L[R[c]]=L[c]; for (int i=D[c];i!=c;i=D[i]) for (int j=R[i];j!=i;j=R[j]) { s[col[j]]--; D[U[j]]=D[j]; U[D[j]]=U[j]; } } void resume(int c) { R[L[c]]=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]) { s[col[j]]++; D[U[j]]=j; U[D[j]]=j; } } void dfs(int d) { if (d-1>=ansd) return ; if (R[0]==0) { if (d-1<ansd) ansd=d-1; return; } int c=R[0]; for (int i=R[0];i!=0;i=R[i]) if (s[i]<s[c]) c=i; remove(c); for (int i=D[c];i!=c;i=D[i]) { ans[d]=row[i]; for (int j=R[i];j!=i;j=R[j]) remove(col[j]); dfs(d+1); for (int j=L[i];j!=i;j=L[j]) resume(col[j]); } resume(c); return; } }g; int main() { int t; int n,m,p,sx,sy,ex,ey; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&p); g.init(p,n*m); for (int k=1;k<=p;k++) { scanf("%d%d%d%d",&sx,&sy,&ex,&ey); for (int i=sx+1;i<=ex;i++) for (int j=sy+1;j<=ey;j++) g.link(k,(i-1)*m+j); } g.ansd=INF; g.dfs(1); if (g.ansd<INF) printf("%d\n",g.ansd); else printf("-1\n"); } }