首页 > 代码库 > Dancing Link专题
Dancing Link专题
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("\n");122 }123 else124 printf("NO\n");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\n", dlx.ansd);124 }125 return 0;126 }
Dancing Link专题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。