此题反正我自己是认为poj给的数据范围是有错的，不知道是不是自己太弱了，有大神在的话，欢迎来呸！
其实目的就在于建图，搞的我后来建了一个无比纠结的图，先建立了火柴棍和正方形的一个全图，然后再删除一些火柴和正方形
其实舞蹈链就是一个剪枝的深搜，好好理解就是的。数据n应该大于5的。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 int const N = 200; 6 int n; 7 int des,dnum; 8 int mark[N][N],map[N][N]; 9 int rvis[N],cvis[N]; 10 11 int L[N],R[N],U[N],D[N]; 12 int S[N]; 13 int nCol[N]; 14 int nRow[N]; 15 bool answer[N+1]; 16 int best; 17 bool hash[N]; 18 19 void init(int row,int col) 20 { 21 int r=row; 22 int w=col; 23 for (int i=0;i<=w;i++) 24 { 25 L[i]=i-1; R[i]=i+1; 26 U[i]=D[i]=i; 27 } 28 L[0]=w; 29 R[w]=0; 30 int cnt=w+1; 31 for (int i=0;i<r;i++) 32 { 33 int head=cnt,tail=cnt; 34 for (int j=0;j<w;j++) 35 { 36 int c = j+1; 37 if(map[i][j]==1) 38 { 39 S[c]++; 40 nCol[cnt]=c; 41 nRow[cnt]=i; 42 U[D[c]]=cnt; 43 D[cnt]=D[c]; 44 U[cnt]=c; 45 D[c]=cnt; 46 L[cnt]=tail; R[tail]=cnt; 47 R[cnt]=head; L[head]=cnt; 48 tail=cnt; 49 cnt++; 50 } 51 } 52 } 53 } 54 void Remove(int x) 55 { 56 for (int i=D[x];i!=x;i=D[i]) 57 { 58 L[R[i]]=L[i]; 59 R[L[i]]=R[i]; 60 S[nCol[i]]--; 61 } 62 } 63 void Resume(int x) 64 { 65 for (int i=D[x];i!=x;i=D[i]) 66 { 67 L[R[i]]=R[L[i]]=i; 68 S[nCol[i]]++; 69 } 70 } 71 int Hash() 72 { 73 int ans=0; 74 memset(hash,false,sizeof(hash)); 75 for (int c=R[0];c!=0;c=R[c]) 76 { 77 if (!hash[c]) 78 { 79 hash[c]=1; 80 ans++; 81 for (int i=D[c];i!=c;i=D[i]) 82 for (int j=R[i];j!=i;j=R[j]) 83 hash[nCol[j]]=1; 84 } 85 } 86 return ans; 87 } 88 void dfs(int ans) 89 { 90 if (R[0]==0) 91 { 92 if(ans<best) 93 best=ans; 94 return; 95 } 96 int best2 = ans + Hash(); 97 if (best2 >= best) 98 return; 99 100 int c,minnum=100000; 101 for (int i=R[0];i!=0;i=R[i]) 102 { 103 if (S[i]==0) return; 104 if (S[i]<minnum) 105 { 106 minnum=S[i]; 107 c=i; 108 } 109 } 110 for (int i=U[c];i!=c;i=U[i]) 111 { 112 answer[nRow[i]]=true; 113 Remove(i); 114 for (int j=R[i];j!=i;j=R[j]) 115 {Remove(j);} 116 dfs(ans+1); 117 for (int j=L[i];j!=i;j=L[j]) 118 {Resume(j);} 119 Resume(i); 120 answer[nRow[i]]=false; 121 } 122 } 123 int main() 124 { 125 int T; 126 scanf("%d",&T); 127 while(T--) 128 { 129 scanf("%d",&n); 130 memset(mark,0,sizeof(mark)); 131 int i,j,k,si,num=0,ct=0; 132 for(si=1; si<=n; si++) 133 { 134 for(i=1; i<=n-si+1; i++) 135 { 136 for(j=1; j<=n-si+1; j++) 137 { 138 for(k=0; k<si; k++) 139 { 140 mark[(i-1)*(2*n+1)+j+k-1][ct]=1; 141 mark[(i-1+si)*(2*n+1)+j+k-1][ct]=1; 142 mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)-1][ct]=1; 143 mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)+si-1][ct]=1; 144 } 145 ct++; 146 } 147 } 148 } 149 scanf("%d",&dnum); 150 memset(rvis,0,sizeof(rvis)); 151 memset(cvis,0,sizeof(cvis)); 152 memset(map,0,sizeof(map)); 153 for(i=0;i<dnum;i++) 154 { 155 scanf("%d",&des); 156 rvis[des-1]=1; 157 for(j=0;j<ct;j++) 158 { 159 if(mark[des-1][j]==1) 160 { 161 if(!cvis[j]) 162 cvis[j]=1; 163 } 164 } 165 } 166 int row=0,col=0,maxr=2*n*n+2*n; 167 for(i=0;i<maxr;i++) 168 { 169 if(rvis[i])continue; 170 col=0; 171 int f=1; 172 for(j=0;j<ct;j++) 173 { 174 if(cvis[j])continue; 175 if(mark[i][j])f=0; 176 map[row][col++]=mark[i][j]; 177 } 178 row++; 179 if(f)row--; 180 } 181 init(row,col); 182 best=10000; 183 dfs(0); 184 printf("%d ",best); 185 } 186 return 0; 187 }