首页 > 代码库 > HUST 1017 Exact cover DLX
HUST 1017 Exact cover DLX
题意：一个n×m行的矩阵，每个格子可能是 0 或者1 现在让你选择 几列 使得 每一列 有且只有一个1.（精确覆盖模板题）
解题思路：
dancing links 模板
关于dancing links 献上几篇必看论文 ：http://par.buaa.edu.cn/acm-icpc/filepool/r/35/
板子用的kuangbin的板子（还是适牛的。。）
解题思路：
1 // File Name: hust1017.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月04日 星期六 16时47分57秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 const int maxnode = 100010; 26 const int MaxM = 1010; 27 const int MaxN = 1010; 28 using namespace std; 29 struct DLX 30 { 31 int n ,m ,size; 32 int L[maxnode],R[maxnode],U[maxnode],D[maxnode],Row[maxnode],Col[maxnode]; 33 int ansd,ans[MaxN]; 34 int H[MaxN],S[MaxM]; 35 void init(int _n,int _m) 36 { 37 n = _n; 38 m = _m; 39 for(int i = 0;i <= m;i++) 40 { 41 S[i] = 0; // S 代表的是每一列的颜色 42 U[i] = D[i] = i; 43 L[i] = i-1; 44 R[i] = i+1; 45 } 46 R[m] = 0; L[0] = m; 47 size = m; 48 for(int i = 1;i <= n;i++) 49 H[i] = -1; // H[i] 代表第I 行的头 50 } 51 void Link(int r,int c) 52 { 53 ++S[Col[++size]=c]; 54 Row[size] = r; 55 D[size] = D[c]; 56 U[D[c]] = size; 57 U[size] = c; 58 D[c] = size; 59 if(H[r] < 0)H[r] = L[size] = R[size] = size; 60 else 61 { 62 R[size] = R[H[r]]; 63 L[R[H[r]]] = size; 64 L[size] = H[r]; 65 R[H[r]] = size; // 插入到 H[r] 的右边 66 } 67 } 68 void remove(int c) //列为单位，横向 69 { 70 L[R[c]] = L[c]; R[L[c]] = R[c]; 71 for(int i = D[c];i != c;i = D[i]) 72 for(int j = R[i];j != i;j = R[j]) 73 { 74 U[D[j]] = U[j]; 75 D[U[j]] = D[j]; 76 --S[Col[j]]; 77 }//删除一列，k行 78 } 79 void resume(int c) 80 { 81 L[R[c]] = R[L[c]] = c; 82 for(int i = U[c];i != c; i = U[i]) 83 for(int j = L[i];j != i ;j = L[j]) 84 { 85 U[D[j]] = j; 86 D[U[j]] = j; 87 ++S[Col[j]]; 88 } 89 } 90 bool Dance(int d) 91 { 92 if(R[0] == 0 ) 93 { 94 ansd = d; //答案长度 95 return true; 96 } 97 int c = R[0]; 98 for(int i = R[c];i != 0 ;i = R[i]) 99 if(S[i] < S[c])100 c = i ; 101 remove(c);102 for(int i = D[c]; i != c;i = D[i])103 {104 ans[d] = Row[i];105 for(int j = R[i]; j != i ;j = R[j]) remove(Col[j]);106 if(Dance(d+1)) return true;107 for(int j = L[i]; j != i ;j = L[j]) resume(Col[j]);108 }109 resume(c);110 return false;111 }112 };113 114 DLX g;115 int main(){116 int n , m ; 117 while(scanf("%d %d",&n,&m) != EOF)118 {119 g.init(n,m);120 int num, j; 121 for(int i = 1;i <= n;i ++)122 {123 scanf("%d",&num);124 while(num--)125 {126 scanf("%d",&j);127 g.Link(i,j);128 }129 }130 if(!g.Dance(0)) printf("NO\n");131 else{132 printf("%d ",g.ansd);133 for(int i = 0;i < g.ansd;i ++)134 printf(" %d",g.ans[i]);135 printf("\n"); 136 }137 138 }139 return 0;140 }
HUST 1017 Exact cover DLX
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。