[POJ 3740] Easy Finding【DLX】
Problem:
Time Limit: 1000MS | Memory Limit: 65536K |
Description
Input
Output
Sample Input
3 3 0 1 0 0 0 1 1 0 0 4 4 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0
Sample Output
Yes, I found it It is impossible
Source
Solution:
这道题实际上可以直接 DFS 水过的。。然而我还是要认真研究 Dancing Links。
Dancing Links 是我们伟大的先驱高德纳 (Donald Knuth) 先生为了解决精确覆盖问题 (Exact Cover Problem) 所提出的 Algorithm X 中所用到的数据结构,其本质是一个双向循环十字链表。
上图即为 Dancing Links 的模型,其中 h 为链表头,A ~ G 为列首,其余的每个点代表一个 1。
对于每个节点 i,需要维护其上下左右的四个节点 U[i], D[i], L[i], R[i] 以及所属列的列首 C[i]。
对于每一列 c,需要维护列元素数 S[c](即上图中列首所标的数)。
ALGORITHM X(Depth, Matrix): if Matrix.empty() return true choose a column c with the least number of elements remove column c and each row r such that Matrix[r][c] == 1 for each row r such that Matrix[r][c] == 1 record row r in the solution for each column j such that Matrix[r][j] == 1 remove column j and each row i such that Matrix[i][j] == 1 if X(Depth + 1, Matrix) == true return true for each column j such that Matrix[r][j] == 1 restore column j and each row i such that Matrix[i][j] == 1 restore column c and each row r such that Matrix[r][c] == 1 return false
上述伪代码即为搜索的改进原理,其核心为移除 (remove) 和恢复 (restore) 操作。
而 Dancing Links 可以简便地实现这两个操作。
【移除 (remove) 操作】
remove(c) // Remove the i-th column L[R[c]] = L[c] R[L[c]] = R[c] for each point i in column c, enumerated forward for each point j in the same row as i, enumerated forward U[D[j]] = U[j] D[U[j]] = D[j] S[C[j]]--;
【恢复 (restore) 操作】
restore(c) // Restore the i-th column L[R[c]] = c R[L[c]] = c for each point i in column c, enumerated backward for each point j in the same row as i, enumerated backward U[D[j]] = j D[U[j]] = j S[C[j]]++;
搜索时,Dancing Links 的矩阵通常缩小得很快,所以能优化时间。
需要细细体会一番 ~~
更详细的解释参见 http://blog.csdn.net/xiexingshishu/article/details/43064259。
Code: O(玄学) [748K, 266MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int M, N, A; int col[305], col_size; struct Dancing_Link{ // The 0-th point is the head of dancing link int S[5000], C[5000]; // S[i]: The remaining number of the i-th column // C[i]: The column in which the i-th point is int U[5000], D[5000], L[5000], R[5000]; int topv; inline void init(int col_num){ // Initialize col_num column heads topv = col_num; memset(S, 0, sizeof(S)); for(register int i = 0; i <= col_num; i++) C[i] = U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1; L[0] = col_num, R[col_num] = 0; } inline void del(int c){ // Remove the i-th column L[R[c]] = L[c], R[L[c]] = R[c]; for(register int i = D[c]; i != c; i = D[i]) for(register int j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], S[C[j]]--; } inline void add(int c){ // Restore the i-th column L[R[c]] = R[L[c]] = c; for(register int i = U[c]; i != c; i = U[i]) for(register int j = L[i]; j != i; j = L[j]) U[D[j]] = D[U[j]] = j, S[C[j]]++; } inline void addline(int *col, int col_size){ // Add a new line if(!col_size) return; for(register int i = 1; i <= col_size; i++){ int &c = col[i]; C[++topv] = c; L[topv] = topv - 1, R[topv] = topv + 1; U[topv] = U[c], D[U[c]] = topv; D[topv] = c, U[c] = topv; S[c]++; } L[topv - col_size + 1] = topv, R[topv] = topv - col_size + 1; } inline bool dance(){ // Dance to search for the solution if(R[0] == 0) return 1; // The link is empty int c = R[0]; for(register int i = R[c]; i; i = R[i]) if(S[i] < S[c]) c = i; // Find the column with the least points del(c); for(register int i = D[c]; i != c; i = D[i]){ // Try every line // We could record the chosen line here if necessary for(register int j = R[i]; j != i; j = R[j]) del(C[j]); if(dance()) return 1; for(register int j = L[i]; j != i; j = L[j]) add(C[j]); } add(c); return 0; } } dl; int main(){ while(scanf("%d%d", &M, &N) != EOF){ dl.init(N); for(register int i = 1; i <= M; i++){ col_size = 0; for(register int j = 1; j <= N; j++){ scanf("%d", &A); if(A) col[++col_size] = j; } dl.addline(col, col_size); } if(dl.dance()) puts("Yes, I found it"); else puts("It is impossible"); } return 0; }
发表评论