poj 1084 舞蹈链（纠结题）

此题反正我自己是认为poj给的数据范围是有错的，不知道是不是自己太弱了，有大神在的话，欢迎来呸！

其实目的就在于建图，搞的我后来建了一个无比纠结的图，先建立了火柴棍和正方形的一个全图，然后再删除一些火柴和正方形

其实舞蹈链就是一个剪枝的深搜，好好理解就是的。数据n应该大于5的。

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 int const N = ;

 int n;

 int des,dnum;

 int mark[N][N],map[N][N];

 int rvis[N],cvis[N];

 int L[N],R[N],U[N],D[N];

 int S[N];

 int nCol[N];

 int nRow[N];

 bool answer[N+];

 int best;

 bool hash[N];

 void init(int row,int col)

 {

     int r=row;

     int w=col;

     for (int i=;i<=w;i++)

     {

         L[i]=i-; R[i]=i+;

         U[i]=D[i]=i;

     }

     L[]=w;

     R[w]=;

     int cnt=w+;

     for (int i=;i<r;i++)

     {

         int head=cnt,tail=cnt;

         for (int j=;j<w;j++)

         {

             int c = j+;

             if(map[i][j]==)

             {

                 S[c]++;

                 nCol[cnt]=c;

                 nRow[cnt]=i;

                 U[D[c]]=cnt;

                 D[cnt]=D[c];

                 U[cnt]=c;

                 D[c]=cnt;

                 L[cnt]=tail; R[tail]=cnt;

                 R[cnt]=head; L[head]=cnt;

                 tail=cnt;

                 cnt++;

             }

         }

     }

 }

 void Remove(int x)

 {

     for (int i=D[x];i!=x;i=D[i])

     {

         L[R[i]]=L[i];

         R[L[i]]=R[i];

         S[nCol[i]]--;

     }

 }

 void Resume(int x)

 {

     for (int i=D[x];i!=x;i=D[i])

     {

         L[R[i]]=R[L[i]]=i;

         S[nCol[i]]++;

     }

 }

 int Hash()

 {

     int ans=;

     memset(hash,false,sizeof(hash));

     for (int c=R[];c!=;c=R[c])

     {

         if (!hash[c])

         {

             hash[c]=;

             ans++;

             for (int i=D[c];i!=c;i=D[i])

                 for (int j=R[i];j!=i;j=R[j])

                     hash[nCol[j]]=;

         }

     }

     return ans;

 }

 void dfs(int ans)

 {

     if (R[]==)

     {

         if(ans<best)

         best=ans;

         return;

     }

     int best2 = ans + Hash();

     if (best2 >= best)

         return;

     int c,minnum=;

     for (int i=R[];i!=;i=R[i])

     {

         if (S[i]==) return;

         if (S[i]<minnum)

         {

             minnum=S[i];

             c=i;

         }

     }

     for (int i=U[c];i!=c;i=U[i])

     {

         answer[nRow[i]]=true;

         Remove(i);

         for (int j=R[i];j!=i;j=R[j])

             {Remove(j);}

         dfs(ans+);

         for (int j=L[i];j!=i;j=L[j])

             {Resume(j);}

         Resume(i);

         answer[nRow[i]]=false;

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         memset(mark,,sizeof(mark));

         int i,j,k,si,num=,ct=;

         for(si=; si<=n; si++)

         {

             for(i=; i<=n-si+; i++)

             {

                 for(j=; j<=n-si+; j++)

                 {

                     for(k=; k<si; k++)

                     {

                         mark[(i-)*(*n+)+j+k-][ct]=;

                         mark[(i-+si)*(*n+)+j+k-][ct]=;

                         mark[i*n+(i-)*(n+)+j+k*(*n+)-][ct]=;

                         mark[i*n+(i-)*(n+)+j+k*(*n+)+si-][ct]=;

                     }

                     ct++;

                 }

             }

         }

         scanf("%d",&dnum);

         memset(rvis,,sizeof(rvis));

         memset(cvis,,sizeof(cvis));

         memset(map,,sizeof(map));

         for(i=;i<dnum;i++)

         {

             scanf("%d",&des);

             rvis[des-]=;

             for(j=;j<ct;j++)

             {

                 if(mark[des-][j]==)

                 {

                    if(!cvis[j])

                    cvis[j]=;

                 }

             }

         }

         int row=,col=,maxr=*n*n+*n;

         for(i=;i<maxr;i++)

         {

             if(rvis[i])continue;

             col=;

             int f=;

             for(j=;j<ct;j++)

             {

                 if(cvis[j])continue;

                 if(mark[i][j])f=;

                 map[row][col++]=mark[i][j];

             }

             row++;

             if(f)row--;

         }

         init(row,col);

         best=;

         dfs();

         printf("%d\n",best);

     }

     return ;

 }