首页 > 代码库 > POJ 3740 Easy Finding DLX
POJ 3740 Easy Finding DLX
题意:给你一个0,1矩阵 ,求精确覆盖
解题思路:
DLX
解题代码:
1 // File Name: poj3740.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月04日 星期六 20时06分31秒 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 26 using namespace std; 27 const int maxnode = 50000; 28 const int MaxN = 18; 29 const int MaxM = 400; 30 struct DLX 31 { 32 int n , m , size; 33 int U[maxnode],D[maxnode],L[maxnode],R[maxnode],Row[maxnode],Col[maxnode]; 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 ; 42 U[i] = i ; 43 D[i] = i ; 44 L[i] = i-1; 45 R[i] = i+1; 46 } 47 size = m ; 48 L[0] = m; 49 R[m] = 0 ; 50 memset(H,-1,sizeof(H)); 51 } 52 void Link(int r, int c) 53 { 54 ++S[Col[++size] = c]; 55 Row[size] = r; 56 D[size] = D[c]; 57 U[D[c]] = size; 58 U[size] = c; 59 D[c] = size ; 60 if(H[r] < 0) H[r] = L[size] = R[size] = size; 61 else{ 62 R[size] = R[H[r]]; 63 L[R[H[r]]] = size; 64 L[size] = H[r]; 65 R[H[r]] = size; 66 } 67 } 68 void remove(int c) 69 { 70 L[R[c]] = L[c]; 71 R[L[c]] = R[c]; 72 for(int i = D[c]; i != c ;i = D[i]) 73 for(int j = R[i]; j != i ;j = R[j]) 74 { 75 U[D[j]] = U[j]; 76 D[U[j]] = D[j]; 77 --S[Col[j]]; 78 } 79 } 80 void resume(int c) 81 { 82 L[R[c]] = c; 83 R[L[c]] = c; 84 for(int i = D[c];i != c;i = D[i]) 85 for(int j = R[i]; j != i ;j = R[j]) 86 { 87 U[D[j]] = j ; 88 D[U[j]] = j; 89 ++ S[Col[j]]; 90 } 91 } 92 bool Dance() 93 { 94 if(R[0] == 0 ) 95 { 96 return true; 97 } 98 int c = R[0]; 99 for(int i = R[c];i != 0 ;i = R[i])100 if(S[i] < S[c])101 c = i ; 102 remove(c);103 for(int i = D[c];i != c;i = D[i])104 {105 for(int j = R[i];j != i ;j = R[j]) remove(Col[j]);106 if(Dance()) return true;107 for(int j = R[i];j != i; j = R[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 t ;121 for(int i = 1;i <= n;i ++)122 for(int j = 1;j <= m;j ++)123 {124 scanf("%d",&t);125 if(t)126 g.Link(i,j);127 }128 if(g.Dance()) 129 printf("Yes, I found it\n");130 else printf("It is impossible\n");131 }132 return 0;133 }
POJ 3740 Easy Finding DLX
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。