UVA

给你一个n*n的由火柴组成的正方形网格，从中预先拿掉一些火柴，问至少还需要拿掉多少火柴才能破坏掉所有的正方形。

看到这道题，我第一反应就是——把每根火柴和它能破坏掉的正方形连边，不就是个裸的DLX了吗？二话不说直接把我以前写过的DLX板子拿了过来。不过这个问题是可重复覆盖而不是精确覆盖，其实只需要在精确覆盖的基础上稍作修改就行了。

建图方法：枚举出网格完整时所有的火柴和正方形，给它们编上号，除了被拿掉的火柴和已经被破坏掉的正方形，其余的所有火柴和它能破坏掉的正方形连边。

注意跑DLX前要先把所有的空列清掉，否则会死循环。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int N=1000,inf=0x3f3f3f3f;
  5 struct D {
  6     int x[2],y[2];
  7     bool isbound(D& b) {
  8         for(int i=0; i<2; ++i) {
  9             if(x[i]>b.x[0]&&x[i]<b.x[1]&&y[i]>b.y[0]&&y[i]<b.y[1])return 0;
 10             if(x[i]<b.x[0]||x[i]>b.x[1]||y[i]<b.y[0]||y[i]>b.y[1])return 0;
 11         }
 12         return 1;
 13     }
 14 } rod[N],sqr[N];
 15 int n,nrod,nsqr,delrod[N],delsqr[N],m;
 16 struct DLX {
 17     static const int N=1000;
 18     static const int M=1000;
 19     static const int MX=1000;
 20     int n,tot,S[M],H[N],vis[M],ans;
 21     int row[MX],col[MX],L[MX],R[MX],U[MX],D[MX];
 22     void init(int _n) {
 23         n=_n;
 24         for(int i=0; i<=n; ++i) {
 25             U[i]=D[i]=i;
 26             L[i]=i-1,R[i]=i+1;
 27         }
 28         L[0]=n,R[n]=0;
 29         tot=n+1;
 30         memset(S,0,sizeof S);
 31         memset(H,-1,sizeof H);
 32         memset(vis,0,sizeof vis);
 33         ans=inf;
 34     }
 35     void link(int r,int c) {
 36         int u=tot++;
 37         S[c]++;
 38         row[u]=r,col[u]=c;
 39         U[u]=U[c],D[u]=c;
 40         U[D[u]]=D[U[u]]=u;
 41         if(!~H[r])H[r]=L[u]=R[u]=u;
 42         else {
 43             R[u]=H[r],L[u]=L[H[r]];
 44             L[R[u]]=R[L[u]]=u;
 45         }
 46     }
 47     void remove(int c) {
 48         for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];
 49     }
 50     void restore(int c) {
 51         for(int i=U[c]; i!=c; i=U[i])L[R[i]]=R[L[i]]=i;
 52     }
 53     int h() {
 54         int ret=0;
 55         for(int c=R[0]; c!=0; c=R[c])vis[c]=1;
 56         for(int c=R[0]; c!=0; c=R[c])if(vis[c]) {
 57                 ++ret,vis[c]=0;
 58                 for(int i=D[c]; i!=c; i=D[i])
 59                     for(int j=R[i]; j!=i; j=R[j])vis[col[j]]=0;
 60             }
 61         return ret;
 62     }
 63     void check() {
 64         for(int c=1; c<=n; ++c)if(!S[c]) {
 65                 for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];
 66                 L[R[c]]=L[c],R[L[c]]=R[c];
 67             }
 68     }
 69     void dfs(int dep) {
 70         if(R[0]==0) {ans=dep; return;};
 71         if(dep+h()>ans)return;
 72         int c=R[0];
 73         for(int i=R[0]; i!=0; i=R[i])if(S[i]<S[c])c=i;
 74         for(int i=D[c]; i!=c; i=D[i]) {
 75             remove(i);
 76             for(int j=R[i]; j!=i; j=R[j])remove(j);
 77             dfs(dep+1);
 78             for(int j=L[i]; j!=i; j=L[j])restore(j);
 79             restore(i);
 80         }
 81     }
 82 } dlx;
 83 
 84 int main() {
 85     int T;
 86     for(scanf("%d",&T); T--;) {
 87         scanf("%d",&n);
 88         nrod=nsqr=0;
 89         for(int i=0; i<=n; ++i) {
 90             for(int j=0; j<=n; ++j)if(j+1<=n)rod[nrod++]= {i,i,j,j+1};
 91             for(int j=0; j<=n; ++j)if(i+1<=n)rod[nrod++]= {i,i+1,j,j};
 92         }
 93         for(int i=0; i<=n; ++i)
 94             for(int j=0; j<=n; ++j)
 95                 for(int w=1; w<=n; ++w)
 96                     if(i+w<=n&&j+w<=n)sqr[nsqr++]= {i,i+w,j,j+w};
 97         memset(delrod,0,sizeof delrod);
 98         memset(delsqr,0,sizeof delsqr);
 99         scanf("%d",&m);
100         while(m--) {
101             int x;
102             scanf("%d",&x);
103             delrod[x-1]=1;
104             for(int j=0; j<nsqr; ++j)
105                 if(rod[x-1].isbound(sqr[j]))delsqr[j]=1;
106         }
107         dlx.init(nsqr);
108         for(int i=0; i<nrod; ++i)if(!delrod[i])
109                 for(int j=0; j<nsqr; ++j)if(!delsqr[j])
110                         if(rod[i].isbound(sqr[j]))
111                             dlx.link(i+1,j+1);
112         dlx.check();
113         dlx.dfs(0);
114         printf("%d
",dlx.ans);
115     }
116     return 0;
117 }

View Code

以上是普通DLX可重复覆盖的代码，也可以用IDA*优化一下，代码基本一致：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int N=1000;
  5 struct D {
  6     int x[2],y[2];
  7     bool isbound(D& b) {
  8         for(int i=0; i<2; ++i) {
  9             if(x[i]>b.x[0]&&x[i]<b.x[1]&&y[i]>b.y[0]&&y[i]<b.y[1])return 0;
 10             if(x[i]<b.x[0]||x[i]>b.x[1]||y[i]<b.y[0]||y[i]>b.y[1])return 0;
 11         }
 12         return 1;
 13     }
 14 } rod[N],sqr[N];
 15 int n,nrod,nsqr,delrod[N],delsqr[N],m;
 16 struct DLX {
 17     static const int N=1000;
 18     static const int M=1000;
 19     static const int MX=1000;
 20     int n,tot,S[M],H[N],vis[M];
 21     int row[MX],col[MX],L[MX],R[MX],U[MX],D[MX];
 22     void init(int _n) {
 23         n=_n;
 24         for(int i=0; i<=n; ++i) {
 25             U[i]=D[i]=i;
 26             L[i]=i-1,R[i]=i+1;
 27         }
 28         L[0]=n,R[n]=0;
 29         tot=n+1;
 30         memset(S,0,sizeof S);
 31         memset(H,-1,sizeof H);
 32         memset(vis,0,sizeof vis);
 33     }
 34     void link(int r,int c) {
 35         int u=tot++;
 36         S[c]++;
 37         row[u]=r,col[u]=c;
 38         U[u]=U[c],D[u]=c;
 39         U[D[u]]=D[U[u]]=u;
 40         if(!~H[r])H[r]=L[u]=R[u]=u;
 41         else {
 42             R[u]=H[r],L[u]=L[H[r]];
 43             L[R[u]]=R[L[u]]=u;
 44         }
 45     }
 46     void remove(int c) {
 47         for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];
 48     }
 49     void restore(int c) {
 50         for(int i=U[c]; i!=c; i=U[i])L[R[i]]=R[L[i]]=i;
 51     }
 52     int h() {
 53         int ret=0;
 54         for(int c=R[0]; c!=0; c=R[c])vis[c]=1;
 55         for(int c=R[0]; c!=0; c=R[c])if(vis[c]) {
 56                 ++ret,vis[c]=0;
 57                 for(int i=D[c]; i!=c; i=D[i])
 58                     for(int j=R[i]; j!=i; j=R[j])vis[col[j]]=0;
 59             }
 60         return ret;
 61     }
 62     void check() {
 63         for(int c=1; c<=n; ++c)if(!S[c]) {
 64                 for(int i=D[c]; i!=c; i=D[i])L[R[i]]=L[i],R[L[i]]=R[i];
 65                 L[R[c]]=L[c],R[L[c]]=R[c];
 66             }
 67     }
 68     bool dfs(int dep,int mxd) {
 69         if(R[0]==0)return 1;
 70         if(dep+h()>mxd)return 0;
 71         int c=R[0];
 72         for(int i=R[0]; i!=0; i=R[i])if(S[i]<S[c])c=i;
 73         for(int i=D[c]; i!=c; i=D[i]) {
 74             remove(i);
 75             for(int j=R[i]; j!=i; j=R[j])remove(j);
 76             if(dfs(dep+1,mxd))return 1;
 77             for(int j=L[i]; j!=i; j=L[j])restore(j);
 78             restore(i);
 79         }
 80         return 0;
 81     }
 82     int IDAStar() {for(int mxd=0;; ++mxd) {if(dfs(0,mxd))return mxd;}}
 83 } dlx;
 84 
 85 int main() {
 86     int T;
 87     for(scanf("%d",&T); T--;) {
 88         scanf("%d",&n);
 89         nrod=nsqr=0;
 90         for(int i=0; i<=n; ++i) {
 91             for(int j=0; j<=n; ++j)if(j+1<=n)rod[nrod++]= {i,i,j,j+1};
 92             for(int j=0; j<=n; ++j)if(i+1<=n)rod[nrod++]= {i,i+1,j,j};
 93         }
 94         for(int i=0; i<=n; ++i)
 95             for(int j=0; j<=n; ++j)
 96                 for(int w=1; w<=n; ++w)
 97                     if(i+w<=n&&j+w<=n)sqr[nsqr++]= {i,i+w,j,j+w};
 98         memset(delrod,0,sizeof delrod);
 99         memset(delsqr,0,sizeof delsqr);
100         scanf("%d",&m);
101         while(m--) {
102             int x;
103             scanf("%d",&x);
104             delrod[x-1]=1;
105             for(int j=0; j<nsqr; ++j)
106                 if(rod[x-1].isbound(sqr[j]))delsqr[j]=1;
107         }
108         dlx.init(nsqr);
109         for(int i=0; i<nrod; ++i)if(!delrod[i])
110                 for(int j=0; j<nsqr; ++j)if(!delsqr[j])
111                         if(rod[i].isbound(sqr[j]))
112                             dlx.link(i+1,j+1);
113         dlx.check();
114         printf("%d
",dlx.IDAStar());
115     }
116     return 0;
117 }

View Code

感觉对于这种裸的可重复覆盖而言，DLX除了板子代码长了点外就没什么缺点了，直接无脑建图就行了~~