一些链接：
http://www.cnblogs.com/-sunshine/p/3358922.html
http://www.cnblogs.com/grenet/p/3145800.html
1、hust 1017 Exact cover (Dancing Links 模板题)
题意：n*m的单位矩阵。现在要选一些行，使得这些行的集合中每列只出现一个1.
思路：裸的精确覆盖问题。刷一遍模板。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 //精确覆盖问题的定义：给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1 5 const int MN = 1005;//最大行数 6 const int MM = 1005;//最大列数 7 const int MNN = 1e5 + 5 + MM; //最大点数 8 9 struct DLX 10 { 11 int n, m, si;//n行数m列数si目前有的节点数 12 //十字链表组成部分 13 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 14 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 15 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 16 int ansd, ans[MN]; 17 void init(int _n, int _m) //初始化空表 18 { 19 n = _n; 20 m = _m; 21 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 22 { 23 S[i] = 0; 24 U[i] = D[i] = i; //目前纵向的链是空的 25 L[i] = i - 1; 26 R[i] = i + 1; //横向的连起来 27 } 28 R[m] = 0; L[0] = m; 29 si = m; //目前用了前0~m个结点 30 for (int i = 1; i <= n; i++) 31 H[i] = -1; 32 } 33 void link(int r, int c) //插入点(r,c) 34 { 35 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 36 Row[si] = r;//si该结点的行数为r 37 D[si] = D[c];//向下指向c的下面的第一个结点 38 U[D[c]] = si;//c的下面的第一个结点的上面为si 39 U[si] = c;//si的上面为列指针 40 D[c] = si;//列指针指向的第一个该列中的元素设为si 41 if (H[r]<0)//如果第r行没有元素 42 H[r] = L[si] = R[si] = si; 43 else 44 { 45 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 46 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 47 L[si] = H[r];//si的左侧为行指针 48 R[H[r]] = si;//行指针的右侧为si 49 } 50 } 51 void remove(int c) //列表中删掉c列 52 { 53 L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 54 R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 55 for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 56 for (int j = R[i]; j != i; j = R[j]) 57 {//对于该列的某个元素所在的行进行遍历 58 U[D[j]] = U[j];//把该元素从其所在列中除去 59 D[U[j]] = D[j]; 60 --S[Col[j]];//该元素所在的列数目减一 61 } 62 } 63 void resume(int c) //恢复c列 64 { 65 for (int i = U[c]; i != c; i = U[i])//枚举该列元素 66 for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 67 ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 68 L[R[c]] = R[L[c]] = c;//c列头指针左右相连 69 } 70 bool dance(int d) //选取了d行 71 { 72 if (R[0] == 0)//全部覆盖了 73 { 74 //全覆盖了之后的操作 75 ansd = d; 76 return 1; 77 } 78 int c = R[0];//表头结点指向的第一个列 79 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 80 if (S[i]<S[c])//找到列中元素个数最少的 81 c = i; 82 remove(c);//将该列删去 83 for (int i = D[c]; i != c; i = D[i]) 84 {//枚举该列的元素 85 ans[d] = Row[i];//记录该列元素的行 86 for (int j = R[i]; j != i; j = R[j]) 87 remove(Col[j]);//将该列的某个元素的行上的元素所在的列都删去 88 if (dance(d + 1)) 89 return 1; 90 for (int j = L[i]; j != i; j = L[j]) 91 resume(Col[j]); 92 } 93 resume(c); 94 return 0; 95 } 96 }dlx; 97 98 int main() 99 { 100 int n, m; 101 while (scanf("%d%d", &n, &m) != EOF) 102 { 103 dlx.init(n, m); 104 for (int i = 1; i <= n; i++) 105 {//共n列 106 int k; 107 scanf("%d", &k);//每列中含1的个数 108 while (k--) 109 { 110 int cc; 111 scanf("%d", &cc);//输入其所在的列 112 dlx.link(i, cc);//链接 113 } 114 } 115 dlx.ansd = -1; 116 if (dlx.dance(0)) 117 { 118 printf("%d", dlx.ansd); 119 for (int i = 0; i<dlx.ansd; i++) 120 printf(" %d", dlx.ans[i]); 121 printf(" "); 122 } 123 else 124 printf("NO "); 125 } 126 return 0; 127 }
2、ZOJ 3209 Treasure Map
题意：给出一些矩形，问最少需要多少个矩形可以把指定的一块区域覆盖。
思路：把每个矩形块看成行，把指定区域分成1*1的单元格，所有的单元格看成列。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include<algorithm> 5 //精确覆盖问题的定义：给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1 6 const int MN = 1005;//最大行数 7 const int MM = 1005;//最大列数 8 const int MNN = 1e5 + 5 + MM; //最大点数 9 10 struct DLX 11 { 12 int n, m, si;//n行数m列数si目前有的节点数 13 //十字链表组成部分 14 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 15 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 16 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 17 int ansd, ans[MN]; 18 void init(int _n, int _m) //初始化空表 19 { 20 n = _n; 21 m = _m; 22 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 23 { 24 S[i] = 0; 25 U[i] = D[i] = i; //目前纵向的链是空的 26 L[i] = i - 1; 27 R[i] = i + 1; //横向的连起来 28 } 29 R[m] = 0; L[0] = m; 30 si = m; //目前用了前0~m个结点 31 for (int i = 1; i <= n; i++) 32 H[i] = -1; 33 } 34 void link(int r, int c) //插入点(r,c) 35 { 36 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 37 Row[si] = r;//si该结点的行数为r 38 D[si] = D[c];//向下指向c的下面的第一个结点 39 U[D[c]] = si;//c的下面的第一个结点的上面为si 40 U[si] = c;//si的上面为列指针 41 D[c] = si;//列指针指向的第一个该列中的元素设为si 42 if (H[r]<0)//如果第r行没有元素 43 H[r] = L[si] = R[si] = si; 44 else 45 { 46 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 47 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 48 L[si] = H[r];//si的左侧为行指针 49 R[H[r]] = si;//行指针的右侧为si 50 } 51 } 52 void remove(int c) //列表中删掉c列 53 { 54 L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 55 R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 56 for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 57 for (int j = R[i]; j != i; j = R[j]) 58 {//对于该列的某个元素所在的行进行遍历 59 U[D[j]] = U[j];//把该元素从其所在列中除去 60 D[U[j]] = D[j]; 61 --S[Col[j]];//该元素所在的列数目减一 62 } 63 } 64 void resume(int c) //恢复c列 65 { 66 for (int i = U[c]; i != c; i = U[i])//枚举该列元素 67 for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 68 ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 69 L[R[c]] = R[L[c]] = c;//c列头指针左右相连 70 } 71 bool dance(int d) //选取了d行 72 { 73 if (ansd != -1 && ansd < d)return 0; 74 if (R[0] == 0)//全部覆盖了 75 { 76 //全覆盖了之后的操作 77 if(ansd==-1)ansd = d; 78 else if (d < ansd) ansd = d; 79 return 1; 80 } 81 int c = R[0];//表头结点指向的第一个列 82 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 83 if (S[i]<S[c])//找到列中元素个数最少的 84 c = i; 85 remove(c);//将该列删去 86 for (int i = D[c]; i != c; i = D[i]) 87 {//枚举该列的元素 88 ans[d] = Row[i];//记录该列元素的行 89 for (int j = R[i]; j != i; j = R[j]) 90 remove(Col[j]);//将该列的某个元素的行上的元素所在的列都删去 91 (dance(d + 1)); 92 for (int j = L[i]; j != i; j = L[j]) 93 resume(Col[j]); 94 } 95 resume(c); 96 return 0; 97 } 98 }dlx; 99 100 int main() 101 { 102 int n, m,p; 103 int t; 104 scanf("%d", &t); 105 while (t--) 106 { 107 scanf("%d%d%d", &n, &m, &p); 108 dlx.init(p, n*m);//将块当成行，所有的单元格看成列 109 for (int pp = 1; pp <= p; pp++) 110 { 111 int x1, x2, y1, y2; 112 scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 113 for (int i = x1 + 1; i <= x2; i++) 114 { 115 for (int j = y1 + 1; j <= y2; j++) 116 { 117 dlx.link(pp, (i - 1)*m + j); 118 } 119 } 120 } 121 dlx.ansd = -1; 122 dlx.dance(0); 123 printf("%d ", dlx.ansd); 124 } 125 return 0; 126 }
3、HDU 2295 Radar
题意：给出n个城市，给出m个雷达（都是坐标），要求在使用不超过k个雷达的情况下，并且保证覆盖所有的城市，使得每个雷达的覆盖半径最小。
思路：DLK重复覆盖模板。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 //重复覆盖：找到一些行，使得这些行的集合中每列至少有一个1 5 const int MN = 55;//最大行数 6 const int MM = 55;//最大列数 7 const int MNN = MM*MN+MM+MN+10; //最大点数 8 9 struct DLX 10 { 11 int n, m, si;//n行数m列数si目前有的节点数 12 //十字链表组成部分 13 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 14 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 15 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 16 int ansd, ans[MN]; 17 void init(int _n, int _m) //初始化空表 18 { 19 n = _n; 20 m = _m; 21 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 22 { 23 S[i] = 0; 24 U[i] = D[i] = i; //目前纵向的链是空的 25 L[i] = i - 1; 26 R[i] = i + 1; //横向的连起来 27 } 28 R[m] = 0; L[0] = m; 29 si = m; //目前用了前0~m个结点 30 for (int i = 1; i <= n; i++) 31 H[i] = -1; 32 } 33 void link(int r, int c) //插入点(r,c) 34 { 35 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 36 Row[si] = r;//si该结点的行数为r 37 D[si] = D[c];//向下指向c的下面的第一个结点 38 U[D[c]] = si;//c的下面的第一个结点的上面为si 39 U[si] = c;//si的上面为列指针 40 D[c] = si;//列指针指向的第一个该列中的元素设为si 41 if (H[r]<0)//如果第r行没有元素 42 H[r] = L[si] = R[si] = si; 43 else 44 { 45 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 46 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 47 L[si] = H[r];//si的左侧为行指针 48 R[H[r]] = si;//行指针的右侧为si 49 } 50 } 51 void remove(int c) //列表中删掉c列 52 { 53 //L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 54 //R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 55 //for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 56 // for (int j = R[i]; j != i; j = R[j]) 57 // {//对于该列的某个元素所在的行进行遍历 58 // U[D[j]] = U[j];//把该元素从其所在列中除去 59 // D[U[j]] = D[j]; 60 // --S[Col[j]];//该元素所在的列数目减一 61 // } 62 /*重复覆盖*//*c为元素编号，而非列号*//*即删除该元素所在的列，包括它自身和列头指针*/ 63 for (int i = D[c]; i != c; i = D[i]) 64 { 65 L[R[i]] = L[i], R[L[i]] = R[i]; 66 } 67 } 68 void resume(int c)//恢复c列 69 { 70 //for (int i = U[c]; i != c; i = U[i])//枚举该列元素 71 // for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 72 // ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 73 //L[R[c]] = R[L[c]] = c;//c列头指针左右相连 74 /*重复覆盖*/ 75 for (int i = U[c]; i != c; i = U[i]) 76 { 77 L[R[i]] = R[L[i]] = i; 78 } 79 } 80 int f_check()//精确覆盖区估算剪枝 81 { 82 /* 83 强剪枝。这个 剪枝利用的思想是A*搜索中的估价函数。即，对于当前的递归深度K下的矩阵，估计其最好情况下（即最少还需要多少步）才能出解。也就是，如果将能够覆盖当 前列的所有行全部选中，去掉这些行能够覆盖到的列，将这个操作作为一层深度。重复此操作直到所有列全部出解的深度是多少。如果当前深度加上这个估价函数返 回值，其和已然不能更优（也就是已经超过当前最优解），则直接返回，不必再搜。 84 */ 85 int vis[MNN]; 86 memset(vis, 0, sizeof(vis)); 87 int ret = 0; 88 for (int c = R[0]; c != 0; c = R[c]) vis[c] = true; 89 for (int c = R[0]; c != 0; c = R[c]) 90 if (vis[c]) 91 { 92 ret++; 93 vis[c] = false; 94 for (int i = D[c]; i != c; i = D[i]) 95 for (int j = R[i]; j != i; j = R[j]) 96 vis[Col[j]] = false; 97 } 98 return ret; 99 } 100 bool dance(int d,int limit) //选取了d行,limit为限制选取的最大行数 101 { 102 /*重复覆盖 103 1、如果矩阵为空，得到结果，返回 104 2、从矩阵中选择一列，以选取最少元素的列为优化方式 105 3、删除该列及其覆盖的行 106 4、对该列的每一行元素：删除一行及其覆盖的列， 107 5、进行下一层搜索，如果成功则返回 108 6、恢复现场，跳至4 109 7、恢复所选择行 110 */ 111 if (d > limit)return false; 112 if (d + f_check() > limit)return false; 113 if (R[0] == 0)//全部覆盖了 114 { 115 //全覆盖了之后的操作 116 ansd = d; 117 return true; 118 } 119 int c = R[0];//表头结点指向的第一个列 120 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 121 if (S[i]<S[c])//找到列中元素个数最少的 122 c = i; 123 //remove(c);//将该列删去(精确覆盖) 124 for (int i = D[c]; i != c; i = D[i]) 125 {//枚举该列的元素 126 ans[d] = Row[i];//记录该列元素的行 127 remove(i);//新增(重复覆盖) 128 for (int j = R[i]; j != i; j = R[j]) 129 remove(j);//remove(Col[j])(精确覆盖) 130 if (dance(d + 1, limit)) return true; 131 for (int j = L[i]; j != i; j = L[j]) 132 resume(j);//resume(Col[j])(精确覆盖) 133 resume(i);//新增(重复覆盖) 134 } 135 //resume(c);(精确覆盖) 136 return false; 137 } 138 }dlx; 139 struct node 140 { 141 int x; 142 int y; 143 }citys[55],radar[55]; 144 double dis[55][55]; 145 int main() 146 { 147 int n, m,k; 148 int t; 149 scanf("%d", &t); 150 151 while (t--) 152 { 153 double l = 0, r=0,maxx=0,maxy=0; 154 scanf("%d%d%d", &n, &m, &k); 155 for (int i = 1; i <= n; i++) 156 { 157 scanf("%d%d", &citys[i].x, &citys[i].y); 158 if (citys[i].x + citys[i].y > maxx + maxy) 159 { 160 maxx = citys[i].x, maxy = citys[i].y; 161 } 162 } 163 for (int i = 1; i <= m; i++) 164 { 165 scanf("%d%d", &radar[i].x, &radar[i].y); 166 if (radar[i].x + radar[i].y > maxx + maxy) 167 { 168 maxx = radar[i].x, maxy = radar[i].y; 169 } 170 } 171 for (int i = 1; i <= m; i++) 172 { 173 for (int j = 1; j <= n; j++) 174 { 175 dis[i][j] = sqrt((radar[i].x - citys[j].x)*(radar[i].x - citys[j].x) + (radar[i].y - citys[j].y)*(radar[i].y - citys[j].y)); 176 } 177 } 178 r = sqrt(maxx*maxx + maxy*maxy); 179 while (r - l > 1e-7) 180 { 181 double mid = (l + r) / 2; 182 dlx.init(m, n); 183 for (int i = 1; i <= m; i++) 184 { 185 for (int j = 1; j <= n; j++) 186 { 187 if (dis[i][j] <= mid) dlx.link(i, j); 188 } 189 } 190 dlx.ansd = -1; 191 if (dlx.dance(0,k)) r = mid; 192 else l = mid; 193 } 194 printf("%.6lf ", l); 195 } 196 return 0; 197 }
4、FZU 1686 神龙的难题
题意：有个n*m的矩形，每次可以把n1*m1小矩形范围内的敌人消灭，最少的次数。
思路：DLK重复覆盖模板，枚举所有的小矩形，设为行，把所有敌人编号，记为列。
1 #include<iostream> 2 #include<cstdio> 3 #include<memory.h> 4 #include<algorithm> 5 using namespace std; 6 //重复覆盖：找到一些行，使得这些行的集合中每列至少有一个1 7 const int MN =250;//最大行数 8 const int MM = 250;//最大列数 9 const int MNN = MM*MN; //最大点数 10 11 struct DLX 12 { 13 int n, m, si;//n行数m列数si目前有的节点数 14 //十字链表组成部分 15 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 16 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 17 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 18 int ansd, ans[MN]; 19 void init(int _n, int _m) //初始化空表 20 { 21 n = _n; 22 m = _m; 23 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 24 { 25 S[i] = 0; 26 U[i] = D[i] = i; //目前纵向的链是空的 27 L[i] = i - 1; 28 R[i] = i + 1; //横向的连起来 29 } 30 R[m] = 0; L[0] = m; 31 si = m; //目前用了前0~m个结点 32 for (int i = 1; i <= n; i++) 33 H[i] = -1; 34 } 35 void link(int r, int c) //插入点(r,c) 36 { 37 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 38 Row[si] = r;//si该结点的行数为r 39 D[si] = D[c];//向下指向c的下面的第一个结点 40 U[D[c]] = si;//c的下面的第一个结点的上面为si 41 U[si] = c;//si的上面为列指针 42 D[c] = si;//列指针指向的第一个该列中的元素设为si 43 if (H[r]<0)//如果第r行没有元素 44 H[r] = L[si] = R[si] = si; 45 else 46 { 47 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 48 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 49 L[si] = H[r];//si的左侧为行指针 50 R[H[r]] = si;//行指针的右侧为si 51 } 52 } 53 void remove(int c) //列表中删掉c列 54 { 55 //L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 56 //R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 57 //for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 58 // for (int j = R[i]; j != i; j = R[j]) 59 // {//对于该列的某个元素所在的行进行遍历 60 // U[D[j]] = U[j];//把该元素从其所在列中除去 61 // D[U[j]] = D[j]; 62 // --S[Col[j]];//该元素所在的列数目减一 63 // } 64 /*重复覆盖*//*c为元素编号，而非列号*//*即删除该元素所在的列，包括它自身和列头指针*/ 65 for (int i = D[c]; i != c; i = D[i]) 66 { 67 L[R[i]] = L[i], R[L[i]] = R[i]; 68 } 69 } 70 71 void resume(int c)//恢复c列 72 { 73 //for (int i = U[c]; i != c; i = U[i])//枚举该列元素 74 // for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 75 // ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 76 //L[R[c]] = R[L[c]] = c;//c列头指针左右相连 77 /*重复覆盖*/ 78 for (int i = U[c]; i != c; i = U[i]) 79 { 80 L[R[i]] = R[L[i]] = i; 81 } 82 } 83 84 85 bool vis[MNN]; 86 int f_check()//精确覆盖区估算剪枝 87 { 88 /* 89 强剪枝。这个 剪枝利用的思想是A*搜索中的估价函数。即，对于当前的递归深度K下的矩阵，估计其最好情况下（即最少还需要多少步）才能出解。也就是，如果将能够覆盖当 前列的所有行全部选中，去掉这些行能够覆盖到的列，将这个操作作为一层深度。重复此操作直到所有列全部出解的深度是多少。如果当前深度加上这个估价函数返 回值，其和已然不能更优（也就是已经超过当前最优解），则直接返回，不必再搜。 90 */ 91 92 int ret = 0; 93 for (int c = R[0]; c != 0; c = R[c]) vis[c] = true; 94 for (int c = R[0]; c != 0; c = R[c]) 95 if (vis[c]) 96 { 97 ret++; 98 vis[c] = false; 99 for (int i = D[c]; i != c; i = D[i]) 100 for (int j = R[i]; j != i; j = R[j]) 101 vis[Col[j]] = false; 102 } 103 return ret; 104 } 105 void dance(int d) //选取了d行 106 { 107 /*重复覆盖 108 1、如果矩阵为空，得到结果，返回 109 2、从矩阵中选择一列，以选取最少元素的列为优化方式 110 3、删除该列及其覆盖的行 111 4、对该列的每一行元素：删除一行及其覆盖的列， 112 5、进行下一层搜索，如果成功则返回 113 6、恢复现场，跳至4 114 7、恢复所选择行 115 */ 116 if (d + f_check() >=ansd)return; 117 if (R[0] == 0)//全部覆盖了 118 { 119 //全覆盖了之后的操作 120 if(ansd > d) ansd=d; 121 return; 122 } 123 int c = R[0];//表头结点指向的第一个列 124 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 125 if (S[i]<S[c])//找到列中元素个数最少的 126 c = i; 127 //remove(c);//将该列删去(精确覆盖) 128 for (int i = D[c]; i != c; i = D[i]) 129 {//枚举该列的元素 130 ans[d] = Row[i];//记录该列元素的行 131 remove(i);//新增(重复覆盖) 132 for (int j = R[i]; j != i; j = R[j]) 133 remove(j);//remove(Col[j])(精确覆盖) 134 dance(d + 1); 135 for (int j = L[i]; j != i; j = L[j]) 136 resume(j);//resume(Col[j])(精确覆盖) 137 resume(i);//新增(重复覆盖) 138 } 139 //resume(c);(精确覆盖) 140 } 141 }dlx; 142 int mp[20][20]; 143 int main() 144 { 145 int n, m,n1,m1; 146 while (~scanf("%d%d",&n,&m)) 147 { 148 int cnt = 0; 149 for (int i = 1; i <= n; i++) 150 { 151 for (int j = 1; j <= m; j++) 152 { 153 scanf("%d", &mp[i][j]); 154 if (mp[i][j]) mp[i][j] = ++cnt; 155 } 156 } 157 scanf("%d%d", &n1, &m1); 158 dlx.init(n*m,cnt); 159 cnt = 1; 160 for (int i = 1; i <=n; i++) 161 { 162 for (int j = 1; j <=m; j++) 163 { 164 for (int x = 0; x <n1&&i+x<=n; x++) 165 { 166 for (int z = 0; z < m1&&z+j<=m; z++) 167 { 168 if (mp[i+x][j+z]) dlx.link(cnt, mp[i+x][j+z]); 169 } 170 } 171 cnt++; 172 } 173 } 174 dlx.ansd = 0x3f3f3f3f; 175 dlx.dance(0); 176 printf("%d ", dlx.ansd); 177 } 178 return 0; 179 }
5、poj 1084 Square Destroyer
题意：给出由火柴构成的网格，现在在已经删去若干根火柴后，问最少还需要删去多少火柴，使得网格中的所有正方形被破坏。
思路：DLK重复覆盖，把每根火柴作为行，每个正方形看成列，如果某根火柴可以构成该正方形的一条边，则link.
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define N 60//55个格子 6 #define M 70//60个火柴 7 #define NN 300//每个格子4根火柴，算上辅助是5 8 #define inf 0x3f3f3f3f 9 using namespace std; 10 /*60火柴，25格*/ 11 int ans; 12 struct DLX 13 { 14 int U[NN], D[NN], L[NN], R[NN], C[NN]; 15 int H[M], T[N], cnt; 16 inline void init() 17 { 18 cnt = 0; 19 memset(U, 0, sizeof(U)); 20 memset(D, 0, sizeof(D)); 21 memset(L, 0, sizeof(L)); 22 memset(R, 0, sizeof(R)); 23 memset(C, 0, sizeof(C)); 24 memset(H, 0, sizeof(H)); 25 memset(T, 0, sizeof(T)); 26 } 27 inline void newnode(int x, int y) 28 { 29 C[++cnt] = y; T[y]++; 30 31 if (!H[x])H[x] = L[cnt] = R[cnt] = cnt; 32 else L[cnt] = H[x], R[cnt] = R[H[x]]; 33 R[H[x]] = L[R[H[x]]] = cnt, H[x] = cnt; 34 35 U[cnt] = U[y], D[cnt] = y; 36 U[y] = D[U[y]] = cnt; 37 } 38 int id[N][N][5], eid[2][7][7]; 39 bool destroy[N], map[N][M]; 40 inline void build() 41 { 42 init(); 43 int i, j, k, n, m; 44 int nmrx = 0, npon = 0; 45 scanf("%d%d", &n, &m); 46 memset(destroy, 0, sizeof(destroy)); 47 memset(map, 0, sizeof(map)); 48 for (k = 0; k<n; k++)for (i = 1; i + k <= n; i++)for (j = 1; j + k <= n; j++)id[k][i][j] = ++nmrx; 49 for (i = 1; i <= n; i++) 50 { 51 for (j = 1; j <= n; j++)eid[0][i][j] = ++npon; 52 for (j = 1; j <= n + 1; j++)eid[1][i][j] = ++npon; 53 } 54 for (i = 1; i <= n; i++)eid[0][n + 1][i] = ++npon; 55 for (k = 0; k<n; k++) 56 for (i = 1; i + k <= n; i++) 57 for (j = 1; j + k <= n; j++) 58 { 59 int A = id[k][i][j], temp; 60 for (temp = j; temp <= j + k; temp++)map[A][eid[0][i][temp]] = map[A][eid[0][i + k + 1][temp]] = 1; 61 for (temp = i; temp <= i + k; temp++)map[A][eid[1][temp][j]] = map[A][eid[1][temp][j + k + 1]] = 1; 62 } 63 for (i = 1; i <= m; i++) 64 { 65 scanf("%d", &k); 66 for (j = 1; j <= nmrx; j++)if (map[j][k])destroy[j] = 1; 67 } 68 for (i = 1; i <= nmrx; i++)if (!destroy[i]) 69 { 70 U[i] = D[i] = i; 71 L[i] = L[0], R[i] = 0; 72 L[0] = R[L[0]] = i; 73 } 74 cnt = nmrx; 75 for (i = 1; i <= nmrx; i++) 76 if (!destroy[i]) 77 for (j = 1; j <= npon; j++) 78 if (map[i][j]) 79 newnode(j, i); 80 } 81 inline void remove(int x) 82 { 83 int i = x; 84 do 85 { 86 R[L[i]] = R[i]; 87 L[R[i]] = L[i]; 88 i = D[i]; 89 } while (i != x); 90 } 91 inline void resume(int x) 92 { 93 int i = x; 94 do 95 { 96 R[L[i]] = i; 97 L[R[i]] = i; 98 i = U[i]; 99 } while (i != x); 100 } 101 inline void dfs(int x) 102 { 103 if (x >= ans)return; 104 if (!R[0]) 105 { 106 ans = x; 107 return; 108 } 109 int S = R[0], W = T[S], i, j; 110 int del[N], num; 111 for (i = R[S]; i; i = R[i])if (T[i]<W) 112 { 113 W = T[i]; 114 S = i; 115 } 116 remove(S); 117 for (i = D[S]; i != S; i = D[i]) 118 { 119 del[num = 1] = R[i]; 120 for (j = R[R[i]]; j != R[i]; j = R[j])del[++num] = j; 121 for (j = 1; j <= num; j++)remove(del[j]); 122 dfs(x + 1); 123 for (j = num; j; j--)resume(del[j]); 124 } 125 resume(S); 126 return; 127 } 128 }dlx; 129 int main() 130 { 131 int g; 132 scanf("%d", &g); 133 while (g--) 134 { 135 ans = inf; 136 dlx.build(); 137 dlx.dfs(0); 138 printf("%d ", ans); 139 } 140 return 0; 141 }
6、poj 3074 Sudoku
题意：解9*9的数独。
思路：主要建图，每个不确定格子至多可以填9种数字，一共9*9*9行，对于每个格子，其自身、所在行、所在列、所在块均存在约束，共9*9*4列。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 //精确覆盖问题的定义：给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1 5 const int MN = 9*9*9+10;//最大行数,共有9*9个格子，每个格子可以放1~9 6 const int MM = 9*9+9*9+9*9+9*9+100;//最大列数 7 //用第(i - 1) * 9 + j列为1表示i行j列的已经填数。一共占用81列。 8 //用81 + (i - 1) * 9 + v列表示第i行已经有v这个值。一共占用81列。 9 //用162 + (j - 1) * 9 + v列表示第j列已经有v这个值。一共占用81列。 10 //用243 + (3 * ((i - 1) / 3) + (j + 2) / 3 - 1) + v列表示第3*((i - 1) / 3) + (j + 2) / 3宫格已经有v这个值。一共占用81列。 11 const int MNN = MN*MM; //最大点数 12 13 struct DLX 14 { 15 int n, m, si;//n行数m列数si目前有的节点数 16 //十字链表组成部分 17 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 18 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 19 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 20 int ansd, ans[MN]; 21 void init(int _n, int _m) //初始化空表 22 { 23 n = _n; 24 m = _m; 25 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 26 { 27 S[i] = 0; 28 U[i] = D[i] = i; //目前纵向的链是空的 29 L[i] = i - 1; 30 R[i] = i + 1; //横向的连起来 31 } 32 R[m] = 0; L[0] = m; 33 si = m; //目前用了前0~m个结点 34 for (int i = 1; i <= n; i++) 35 H[i] = -1; 36 } 37 void link(int r, int c) //插入点(r,c) 38 { 39 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 40 Row[si] = r;//si该结点的行数为r 41 D[si] = D[c];//向下指向c的下面的第一个结点 42 U[D[c]] = si;//c的下面的第一个结点的上面为si 43 U[si] = c;//si的上面为列指针 44 D[c] = si;//列指针指向的第一个该列中的元素设为si 45 if (H[r]<0)//如果第r行没有元素 46 H[r] = L[si] = R[si] = si; 47 else 48 { 49 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 50 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 51 L[si] = H[r];//si的左侧为行指针 52 R[H[r]] = si;//行指针的右侧为si 53 } 54 } 55 void remove(int c) //列表中删掉c列 56 { 57 L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 58 R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 59 for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 60 for (int j = R[i]; j != i; j = R[j]) 61 {//对于该列的某个元素所在的行进行遍历 62 U[D[j]] = U[j];//把该元素从其所在列中除去 63 D[U[j]] = D[j]; 64 --S[Col[j]];//该元素所在的列数目减一 65 } 66 } 67 void resume(int c) //恢复c列 68 { 69 for (int i = U[c]; i != c; i = U[i])//枚举该列元素 70 for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 71 ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 72 L[R[c]] = R[L[c]] = c;//c列头指针左右相连 73 } 74 bool dance(int d) //选取了d行 75 { 76 if (R[0] == 0)//全部覆盖了 77 { 78 //全覆盖了之后的操作 79 ansd = d; 80 return 1; 81 } 82 int c = R[0];//表头结点指向的第一个列 83 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 84 if (S[i]<S[c])//找到列中元素个数最少的 85 c = i; 86 remove(c);//将该列删去 87 for (int i = D[c]; i != c; i = D[i]) 88 {//枚举该列的元素 89 ans[d] = Row[i];//记录该列元素的行 90 for (int j = R[i]; j != i; j = R[j]) 91 remove(Col[j]);//将该列的某个元素的行上的元素所在的列都删去 92 if (dance(d + 1)) 93 return 1; 94 for (int j = L[i]; j != i; j = L[j]) 95 resume(Col[j]); 96 } 97 resume(c); 98 return 0; 99 } 100 }dlx; 101 char s[90],path[90]; 102 struct node 103 { 104 int r, c, v; 105 }nds[MN]; 106 int main() 107 { 108 while (~scanf("%s",s)) 109 { 110 if (s[0] == 'e')break; 111 dlx.init(9*9*9,9*9*4); 112 int r=1; 113 for (int i = 1; i <= 9; i++) 114 { 115 for (int j = 1; j <= 9; j++) 116 { 117 if (s[(i - 1) * 9 + j - 1] == '.') 118 { 119 for (int z = 1; z <= 9; z++) 120 { 121 dlx.link(r, (i - 1) * 9 + j); 122 dlx.link(r, 81 + (i - 1) * 9 + z); 123 dlx.link(r, 162 + (j - 1) * 9 + z); 124 dlx.link(r, 243 + (((i - 1) / 3) * 3 + (j + 2) / 3 - 1) * 9 + z); 125 nds[r].r = i, nds[r].c = j, nds[r].v = z; 126 r++; 127 } 128 } 129 else 130 { 131 int z = s[(i - 1) * 9 + j - 1] - '0'; 132 dlx.link(r, (i - 1) * 9 + j); 133 dlx.link(r, 81 + (i - 1) * 9 + z); 134 dlx.link(r, 162 + (j - 1) * 9 + z); 135 dlx.link(r, 243 + (((i - 1) / 3) * 3 + (j + 2) / 3 - 1) * 9 + z); 136 nds[r].r = i, nds[r].c = j, nds[r].v = z; 137 r++; 138 } 139 } 140 } 141 dlx.ansd = -1; 142 dlx.dance(0); 143 int deep = dlx.ansd; 144 for (int i = 0; i < deep; i++) 145 { 146 int posr = dlx.ans[i]; 147 path[(nds[posr].r - 1) * 9 + nds[posr].c - 1] = '0' + nds[posr].v; 148 } 149 path[deep] = ' '; 150 printf("%s ", path); 151 } 152 return 0; 153 } 154 /* 155 .2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534. 156 ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. 157 end 158 */
7、POJ 3076 Sudoku
题意：解16*16的数独。
思路：和上题近似，不过维数从9变为16.
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 //精确覆盖问题的定义：给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1 5 const int MN = 16*16*16 + 10;//最大行数,共有16*16个格子，每个格子可以放1~16（A~P） 6 const int MM = 16*16*4 + 100;//最大列数 7 const int MNN = MN*MM;//最大点数 8 9 struct DLX 10 { 11 int n, m, si;//n行数m列数si目前有的节点数 12 //十字链表组成部分 13 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 14 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 15 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 16 int ansd, ans[MN]; 17 void init(int _n, int _m) //初始化空表 18 { 19 n = _n; 20 m = _m; 21 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 22 { 23 S[i] = 0; 24 U[i] = D[i] = i; //目前纵向的链是空的 25 L[i] = i - 1; 26 R[i] = i + 1; //横向的连起来 27 } 28 R[m] = 0; L[0] = m; 29 si = m; //目前用了前0~m个结点 30 for (int i = 1; i <= n; i++) 31 H[i] = -1; 32 } 33 void link(int r, int c) //插入点(r,c) 34 { 35 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 36 Row[si] = r;//si该结点的行数为r 37 D[si] = D[c];//向下指向c的下面的第一个结点 38 U[D[c]] = si;//c的下面的第一个结点的上面为si 39 U[si] = c;//si的上面为列指针 40 D[c] = si;//列指针指向的第一个该列中的元素设为si 41 if (H[r]<0)//如果第r行没有元素 42 H[r] = L[si] = R[si] = si; 43 else 44 { 45 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 46 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 47 L[si] = H[r];//si的左侧为行指针 48 R[H[r]] = si;//行指针的右侧为si 49 } 50 } 51 void remove(int c) //列表中删掉c列 52 { 53 L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 54 R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 55 for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 56 for (int j = R[i]; j != i; j = R[j]) 57 {//对于该列的某个元素所在的行进行遍历 58 U[D[j]] = U[j];//把该元素从其所在列中除去 59 D[U[j]] = D[j]; 60 --S[Col[j]];//该元素所在的列数目减一 61 } 62 } 63 void resume(int c) //恢复c列 64 { 65 for (int i = U[c]; i != c; i = U[i])//枚举该列元素 66 for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 67 ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 68 L[R[c]] = R[L[c]] = c;//c列头指针左右相连 69 } 70 bool dance(int d) //选取了d行 71 { 72 if (R[0] == 0)//全部覆盖了 73 { 74 //全覆盖了之后的操作 75 ansd = d; 76 return 1; 77 } 78 int c = R[0];//表头结点指向的第一个列 79 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 80 if (S[i]<S[c])//找到列中元素个数最少的 81 c = i; 82 remove(c);//将该列删去 83 for (int i = D[c]; i != c; i = D[i]) 84 {//枚举该列的元素 85 ans[d] = Row[i];//记录该列元素的行 86 for (int j = R[i]; j != i; j = R[j]) 87 remove(Col[j]);//将该列的某个元素的行上的元素所在的列都删去 88 if (dance(d + 1)) 89 return 1; 90 for (int j = L[i]; j != i; j = L[j]) 91 resume(Col[j]); 92 } 93 resume(c); 94 return 0; 95 } 96 }dlx; 97 char s[20]; 98 char path[16 * 16 + 10]; 99 struct node 100 { 101 int r, c, v; 102 }nds[MN]; 103 void addlink(int r, int c, int v, int& cnt) 104 { 105 dlx.link(cnt, (r - 1) * 16 + c); 106 dlx.link(cnt, 16*16 + (r - 1) * 16 + v); 107 dlx.link(cnt, 16*16*2 + (c - 1) * 16 + v); 108 dlx.link(cnt, 16*16*3 + (((r-1)/4)*4+(c-1)/4) * 16 + v); 109 nds[cnt].r = r, nds[cnt].c = c, nds[cnt].v = v; 110 cnt++; 111 } 112 int main() 113 { 114 while (~scanf("%s", s)) 115 { 116 117 dlx.init(16*16*16, 16 * 16 * 4); 118 int r = 1; 119 for (int i = 0; i < 16; i++) 120 { 121 if (s[i] == '-') 122 { 123 for (int k = 1; k <= 16; k++) 124 { 125 addlink(1, i + 1, k,r); 126 } 127 } 128 else 129 { 130 int v = s[i] - 'A' + 1; 131 addlink(1, i + 1, v, r); 132 } 133 } 134 for (int i = 2; i <= 16; i++) 135 { 136 scanf("%s", s); 137 for (int j = 1; j <= 16; j++) 138 { 139 if (s[j-1] == '-') 140 { 141 for (int k = 1; k <= 16; k++) 142 { 143 addlink(i, j, k, r); 144 } 145 } 146 else 147 { 148 int v = s[j-1] - 'A' + 1; 149 addlink(i,j, v, r); 150 } 151 } 152 } 153 dlx.ansd = -1; 154 dlx.dance(0); 155 int deep = dlx.ansd; 156 for (int i = 0; i < deep; i++) 157 { 158 int posr = dlx.ans[i]; 159 path[(nds[posr].r - 1) * 16 + nds[posr].c - 1] = 'A' + nds[posr].v-1; 160 } 161 path[deep] = ' '; 162 for (int i = 0; i < 16; i++) 163 { 164 for (int j = 0; j < 16; j++) printf("%c", path[i * 16 + j]); 165 printf(" "); 166 } 167 printf(" "); 168 } 169 return 0; 170 }
8、hdu 4069 Squiggly Sudoku
题意：解9*9的数独，不过每一块的形状不一定是矩形。
思路：先用DFS分块，然后思路和6相同。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 //精确覆盖问题的定义：给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1 5 const int MN = 9 * 9 * 9 + 10;//最大行数,共有9*9个格子，每个格子可以放1~9 6 const int MM = 9 * 9 + 9 * 9 + 9 * 9 + 9 * 9 + 100;//最大列数 7 //用第(i - 1) * 9 + j列为1表示i行j列的已经填数。一共占用81列。 8 //用81 + (i - 1) * 9 + v列表示第i行已经有v这个值。一共占用81列。 9 //用162 + (j - 1) * 9 + v列表示第j列已经有v这个值。一共占用81列。 10 //用243 + (3 * ((i - 1) / 3) + (j + 2) / 3 - 1) + v列表示第3*((i - 1) / 3) + (j + 2) / 3宫格已经有v这个值。一共占用81列。 11 const int MNN = MN*MM; //最大点数 12 int Count;//几种解决方案 13 bool iscontinue;//当找到两种及以上解决方案时退出 14 struct DLX 15 { 16 int n, m, si;//n行数m列数si目前有的节点数 17 //十字链表组成部分 18 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 19 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 20 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 21 int ansd, ans[MN]; 22 int tans[MN];//保存第一个解决方案 23 void init(int _n, int _m) //初始化空表 24 { 25 n = _n; 26 m = _m; 27 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 28 { 29 S[i] = 0; 30 U[i] = D[i] = i; //目前纵向的链是空的 31 L[i] = i - 1; 32 R[i] = i + 1; //横向的连起来 33 } 34 R[m] = 0; L[0] = m; 35 si = m; //目前用了前0~m个结点 36 for (int i = 1; i <= n; i++) 37 H[i] = -1; 38 } 39 void link(int r, int c) //插入点(r,c) 40 { 41 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 42 Row[si] = r;//si该结点的行数为r 43 D[si] = D[c];//向下指向c的下面的第一个结点 44 U[D[c]] = si;//c的下面的第一个结点的上面为si 45 U[si] = c;//si的上面为列指针 46 D[c] = si;//列指针指向的第一个该列中的元素设为si 47 if (H[r]<0)//如果第r行没有元素 48 H[r] = L[si] = R[si] = si; 49 else 50 { 51 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 52 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 53 L[si] = H[r];//si的左侧为行指针 54 R[H[r]] = si;//行指针的右侧为si 55 } 56 } 57 void remove(int c) //列表中删掉c列 58 { 59 L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 60 R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 61 for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 62 for (int j = R[i]; j != i; j = R[j]) 63 {//对于该列的某个元素所在的行进行遍历 64 U[D[j]] = U[j];//把该元素从其所在列中除去 65 D[U[j]] = D[j]; 66 --S[Col[j]];//该元素所在的列数目减一 67 } 68 } 69 void resume(int c) //恢复c列 70 { 71 for (int i = U[c]; i != c; i = U[i])//枚举该列元素 72 for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 73 ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 74 L[R[c]] = R[L[c]] = c;//c列头指针左右相连 75 } 76 void dance(int d) //选取了d行 77 { 78 if (!iscontinue) return; 79 if (R[0] == 0)//全部覆盖了 80 { 81 //全覆盖了之后的操作 82 ansd = d; 83 if (Count == 0) 84 { 85 memcpy(tans, ans, sizeof(ans)); 86 Count++; 87 } 88 else if (Count == 1) iscontinue = false; 89 return; 90 } 91 int c = R[0];//表头结点指向的第一个列 92 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 93 if (S[i]<S[c])//找到列中元素个数最少的 94 c = i; 95 remove(c);//将该列删去 96 for (int i = D[c]; i != c; i = D[i]) 97 {//枚举该列的元素 98 ans[d] = Row[i];//记录该列元素的行 99 for (int j = R[i]; j != i; j = R[j]) 100 remove(Col[j]);//将该列的某个元素的行上的元素所在的列都删去 101 dance(d + 1); 102 for (int j = L[i]; j != i; j = L[j]) 103 resume(Col[j]); 104 } 105 resume(c); 106 return ; 107 } 108 }dlx; 109 struct node 110 { 111 int r, c, v; 112 }nds[MN]; 113 int dr[] = { 0,0,1,-1 }; 114 int dc[] = { 1,-1,0,0 }; 115 int mp[10][10];//记录值 116 bool wall[10][10][2][2];//记录某个点上下左右是否有墙 117 //[0][0]左，[0][1]右，[1][0]上，[1][1]下 118 int block[10][10];//标记分块 119 int solution[10][10]; 120 void DFS(int r, int c, int flag) 121 { 122 block[r][c] = flag; 123 if (!wall[r][c][0][0]&&!block[r][c-1]) DFS(r, c - 1, flag); 124 if (!wall[r][c][0][1]&&!block[r][c+1]) DFS(r, c + 1, flag); 125 if (!wall[r][c][1][0]&&!block[r-1][c]) DFS(r - 1, c, flag); 126 if (!wall[r][c][1][1]&&!block[r+1][c]) DFS(r + 1, c, flag); 127 } 128 int main() 129 { 130 int t,Case=1; 131 scanf("%d", &t); 132 while (t--) 133 { 134 int num; 135 memset(mp, 0, sizeof(mp)); 136 memset(wall, 0, sizeof(wall)); 137 memset(block, 0, sizeof(block)); 138 for (int i = 1; i <= 9; i++) 139 { 140 for (int j = 1; j <= 9; j++) 141 { 142 scanf("%d", &num); 143 if (num - 128 >= 0) num -= 128, wall[i][j][0][0] = true; 144 if (num - 64 >= 0) num -= 64, wall[i][j][1][1] = true; 145 if (num - 32 >= 0) num -= 32, wall[i][j][0][1] = true; 146 if (num - 16 >= 0) num -= 16, wall[i][j][1][0] = true; 147 mp[i][j] = num; 148 } 149 } 150 int id = 0; 151 for (int i = 1; i <= 9; i++) 152 { 153 for (int j = 1; j <= 9; j++) 154 { 155 if (!block[i][j]) 156 { 157 DFS(i, j, ++id); 158 } 159 } 160 } 161 dlx.init(9 * 9 * 9, 9 * 9 * 4); 162 int Cnt = 1; 163 for (int i = 1; i <= 9; i++) 164 { 165 for (int j = 1; j <= 9; j++) 166 { 167 if (mp[i][j]==0) 168 { 169 for (int z = 1; z <= 9; z++) 170 { 171 dlx.link(Cnt, (i - 1) * 9 + j); 172 dlx.link(Cnt, 81 + (i - 1) * 9 + z); 173 dlx.link(Cnt, 162 + (j - 1) * 9 + z); 174 dlx.link(Cnt, 243 + (block[i][j]-1) * 9 + z); 175 nds[Cnt].r = i, nds[Cnt].c = j, nds[Cnt].v = z; 176 Cnt++; 177 } 178 } 179 else 180 { 181 int z =mp[i][j]; 182 dlx.link(Cnt, (i - 1) * 9 + j); 183 dlx.link(Cnt, 81 + (i - 1) * 9 + z); 184 dlx.link(Cnt, 162 + (j - 1) * 9 + z); 185 dlx.link(Cnt, 243 + (block[i][j]-1) * 9 + z); 186 nds[Cnt].r = i, nds[Cnt].c = j, nds[Cnt].v = z; 187 Cnt++; 188 } 189 } 190 } 191 dlx.ansd = -1; 192 iscontinue = true; 193 Count = 0; 194 dlx.dance(0); 195 printf("Case %d: ", Case++); 196 if (Count == 0) 197 { 198 printf("No solution "); 199 continue; 200 } 201 else if (!iscontinue) 202 { 203 printf("Multiple Solutions "); 204 continue; 205 } 206 int deep = dlx.ansd; 207 for (int i = 0; i < deep; i++) 208 { 209 int posr = dlx.tans[i]; 210 solution[nds[posr].r][nds[posr].c] = nds[posr].v; 211 } 212 for (int i = 1; i <= 9; i++) 213 { 214 for (int j = 1; j <= 9; j++) 215 { 216 printf("%d", solution[i][j]); 217 } 218 printf(" "); 219 } 220 } 221 return 0; 222 }
9、hdu 3335 Divisibility
题意：给出n个数，每次从中取出一个数后，不能再取它的倍数或其因子。问最多能取多少个数，
思路：DLK求极大重复覆盖(因为一个数可能是若干个数的倍数，所以用重复覆盖)。当一个数为另一个数的因子或倍数时，建边。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 //重复覆盖：找到一些行，使得这些行的集合中每列至少有一个1 5 const int MN = 1010;//最大行数 6 const int MM = 1010;//最大列数 7 const int MNN = MM*MN + MM + MN + 10; //最大点数 8 9 struct DLX 10 { 11 int n, m, si;//n行数m列数si目前有的节点数 12 //十字链表组成部分 13 int U[MNN], D[MNN], L[MNN], R[MNN], Row[MNN], Col[MNN]; 14 //第i个结点的U向上指针D下L左R右，所在位置Row行Col列 15 int H[MN], S[MM]; //记录行的选择情况和列的覆盖情况 16 int ansd, ans[MN]; 17 void init(int _n, int _m) //初始化空表 18 { 19 n = _n; 20 m = _m; 21 for (int i = 0; i <= m; i++) //初始化第一横行（表头） 22 { 23 S[i] = 0; 24 U[i] = D[i] = i; //目前纵向的链是空的 25 L[i] = i - 1; 26 R[i] = i + 1; //横向的连起来 27 } 28 R[m] = 0; L[0] = m; 29 si = m; //目前用了前0~m个结点 30 for (int i = 1; i <= n; i++) 31 H[i] = -1; 32 } 33 void link(int r, int c) //插入点(r,c) 34 { 35 ++S[Col[++si] = c]; //si++;Col[si]=c;S[c]++; 36 Row[si] = r;//si该结点的行数为r 37 D[si] = D[c];//向下指向c的下面的第一个结点 38 U[D[c]] = si;//c的下面的第一个结点的上面为si 39 U[si] = c;//si的上面为列指针 40 D[c] = si;//列指针指向的第一个该列中的元素设为si 41 if (H[r]<0)//如果第r行没有元素 42 H[r] = L[si] = R[si] = si; 43 else 44 { 45 R[si] = R[H[r]];//si的右边为行指针所指的右边第一个元素 46 L[R[H[r]]] = si;//行指针所指的右边第一个元素的左侧为si 47 L[si] = H[r];//si的左侧为行指针 48 R[H[r]] = si;//行指针的右侧为si 49 } 50 } 51 void remove(int c) //列表中删掉c列 52 { 53 //L[R[c]] = L[c];//表头操作 //c列头指针的右边的元素的左侧指向c列头指针左边的元素 54 //R[L[c]] = R[c];//c列头指针的左边的元素的右侧指向c列头指针右边的元素 55 //for (int i = D[c]; i != c; i = D[i])//遍历该列的所有元素 56 // for (int j = R[i]; j != i; j = R[j]) 57 // {//对于该列的某个元素所在的行进行遍历 58 // U[D[j]] = U[j];//把该元素从其所在列中除去 59 // D[U[j]] = D[j]; 60 // --S[Col[j]];//该元素所在的列数目减一 61 // } 62 /*重复覆盖*//*c为元素编号，而非列号*//*即删除该元素所在的列，包括它自身和列头指针*/ 63 for (int i = D[c]; i != c; i = D[i]) 64 { 65 L[R[i]] = L[i], R[L[i]] = R[i]; 66 } 67 } 68 void resume(int c)//恢复c列 69 { 70 //for (int i = U[c]; i != c; i = U[i])//枚举该列元素 71 // for (int j = L[i]; j != i; j = L[j])//枚举该列元素所在的行 72 // ++S[Col[U[D[j]] = D[U[j]] = j]];//D[U[j]]=j;U[D[j]]=j;S[Col[j]]++; 73 //L[R[c]] = R[L[c]] = c;//c列头指针左右相连 74 /*重复覆盖*/ 75 for (int i = U[c]; i != c; i = U[i]) 76 { 77 L[R[i]] = R[L[i]] = i; 78 } 79 } 80 int f_check()//精确覆盖区估算剪枝 81 { 82 /* 83 强剪枝。这个 剪枝利用的思想是A*搜索中的估价函数。即，对于当前的递归深度K下的矩阵，估计其最好情况下（即最少还需要多少步）才能出解。也就是，如果将能够覆盖当 前列的所有行全部选中，去掉这些行能够覆盖到的列，将这个操作作为一层深度。重复此操作直到所有列全部出解的深度是多少。如果当前深度加上这个估价函数返 回值，其和已然不能更优（也就是已经超过当前最优解），则直接返回，不必再搜。 84 */ 85 int vis[MNN]; 86 memset(vis, 0, sizeof(vis)); 87 int ret = 0; 88 for (int c = R[0]; c != 0; c = R[c]) vis[c] = true; 89 for (int c = R[0]; c != 0; c = R[c]) 90 if (vis[c]) 91 { 92 ret++; 93 vis[c] = false; 94 for (int i = D[c]; i != c; i = D[i]) 95 for (int j = R[i]; j != i; j = R[j]) 96 vis[Col[j]] = false; 97 } 98 return ret; 99 } 100 void dance(int d) //选取了d行,limit为限制选取的最大行数 101 { 102 /*重复覆盖 103 1、如果矩阵为空，得到结果，返回 104 2、从矩阵中选择一列，以选取最少元素的列为优化方式 105 3、删除该列及其覆盖的行 106 4、对该列的每一行元素：删除一行及其覆盖的列， 107 5、进行下一层搜索，如果成功则返回 108 6、恢复现场，跳至4 109 7、恢复所选择行 110 */ 111 //if (ansd!=-1&&d > ansd)return; 112 //if (ansd!=-1&&d + f_check() >ansd)return; 113 if (R[0] == 0)//全部覆盖了 114 { 115 //全覆盖了之后的操作 116 if(ansd==-1)ansd = d; 117 else if (d > ansd) ansd = d; 118 } 119 int c = R[0];//表头结点指向的第一个列 120 for (int i = R[0]; i != 0; i = R[i])//枚举列头指针 121 if (S[i]<S[c])//找到列中元素个数最少的 122 c = i; 123 //remove(c);//将该列删去(精确覆盖) 124 for (int i = D[c]; i != c; i = D[i]) 125 {//枚举该列的元素 126 ans[d] = Row[i];//记录该列元素的行 127 remove(i);//新增(重复覆盖) 128 for (int j = R[i]; j != i; j = R[j]) 129 remove(j);//remove(Col[j])(精确覆盖) 130 dance(d + 1); 131 for (int j = L[i]; j != i; j = L[j]) 132 resume(j);//resume(Col[j])(精确覆盖) 133 resume(i);//新增(重复覆盖) 134 } 135 //resume(c);(精确覆盖) 136 return; 137 } 138 }dlx; 139 long long num[1010]; 140 int main() 141 { 142 int n; 143 int t; 144 scanf("%d", &t); 145 146 while (t--) 147 { 148 scanf("%d", &n); 149 for (int i = 1; i <= n; i++) 150 { 151 scanf("%lld", &num[i]); 152 } 153 dlx.init(n, n); 154 for (int i = 1; i <=n; i++) 155 { 156 for (int j = 1; j <= n; j++) if (num[i] % num[j] == 0||num[j]%num[i]==0) dlx.link(i, j); 157 } 158 dlx.ansd = -1; 159 dlx.dance(0); 160 printf("%d ",dlx.ansd); 161 } 162 return 0; 163 }
拓展：二分图求最大独立集(选最多的数使得两两之间不能整除)。最大独立集 = 点数 - 二分图最大匹配。
1 #include<iostream> 2 #include<queue> 3 #include<memory.h> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int n,dis,Ny,Nx; 8 const int maxn = 1010;//最大行数 9 const int maxm = 1010;//最大列数 10 const int maxk = 1010; 11 const int INF = 0x7fffffff; 12 bool mp[maxk][maxk];//1表示该ij可以匹配 13 int cx[maxk];//记录x集合中匹配的y元素是哪一个 14 int dx[maxk]; 15 int cy[maxk];//记录y集合中匹配的x元素是哪一个 16 int dy[maxk]; 17 int vis[maxk];//标记该顶点是否访问过 18 bool searchP(void) //BFS 19 { 20 queue <int> Q; 21 dis = INF; 22 memset(dx, -1, sizeof(dx)); 23 memset(dy, -1, sizeof(dy)); 24 for (int i = 1; i <= Nx; i++) 25 if (cx[i] == -1) 26 { 27 Q.push(i); dx[i] = 0; 28 } 29 while (!Q.empty()) 30 { 31 int u = Q.front(); Q.pop(); 32 if (dx[u] > dis) break; //说明该增广路径长度大于dis还没有结束，等待下一次BFS在扩充 33 for (int v = 1; v <= Ny; v++) 34 if (mp[u][v] && dy[v] == -1) 35 { //v是未匹配点 36 dy[v] = dx[u] + 1; 37 if (cy[v] == -1) dis = dy[v]; //得到本次BFS的最大遍历层次 38 else 39 { 40 dx[cy[v]] = dy[v] + 1; //v是匹配点，继续延伸 41 Q.push(cy[v]); 42 } 43 } 44 } 45 return dis != INF; 46 } 47 48 bool DFS(int u) 49 { 50 for (int v = 1; v <= Ny; v++) 51 if (!vis[v] && mp[u][v] && dy[v] == dx[u] + 1) 52 { 53 vis[v] = 1; 54 if (cy[v] != -1 && dy[v] == dis) continue; //层次（也就是增广路径的长度）大于本次查找的dis，是searchP被break的情况，也就是还不确定是否是增广路径，只有等再次调用searchP()在判断。 55 if (cy[v] == -1 || DFS(cy[v])) 56 { //是增广路径，更新匹配集 57 cy[v] = u; cx[u] = v; 58 return 1; 59 } 60 } 61 return 0; 62 } 63 64 int MaxMatch() 65 { 66 int res = 0; 67 memset(cx, -1, sizeof(cx)); 68 memset(cy, -1, sizeof(cy)); 69 while (searchP()) 70 { 71 memset(vis, 0, sizeof(vis)); 72 for (int i = 1; i <= Nx; i++) 73 if (cx[i] == -1 && DFS(i)) res++; //查找到一个增广路径，匹配数res++ 74 } 75 return res; 76 } 77 long long num[1010]; 78 int main() 79 { 80 int C; 81 scanf("%d", &C); 82 int Case = 1; 83 while (C--) 84 { 85 scanf("%d", &n); 86 for (int i = 1; i <= n; i++) scanf("%lld", &num[i]); 87 sort(num + 1, num + 1 + n); 88 memset(mp, 0, sizeof(mp)); 89 for (int i = 1; i <= n; i++) 90 { 91 for (int j = i+1; j <=n; j++) if (num[j] % num[i] == 0) mp[j][i] = 1; 92 } 93 94 Nx = n, Ny =n; 95 int ans = MaxMatch(); 96 printf("%d ", n - ans);//无向二分图：最小路径覆盖数 = "拆点"前原图的顶点数 - 最大匹配数/2 97 } 98 return 0; 99 }