POJ 3740 Easy Finding DLX-白红宇

POJ 3740 Easy Finding DLX

阅读量：5265 次

发布时间：2019-06-14

本文共 2499 字，大约阅读时间需要 8 分钟。

题意：给你一个0,1矩阵，求精确覆盖

解题思路：

DLX

解题代码：

1 // File Name: poj3740.cpp  2 // Author: darkdream  3 // Created Time: 2014年10月04日 星期六 20时06分31秒  4   5 #include
      
         6 #include
       
          7 #include
          8 #include
         
            9 #include
          
            10 #include
           
             11 #include
            
              12 #include
             
               13 #include
              
                14 #include
               
                 15 #include
                
                  16 #include
                 
                   17 #include
                  
                    18 #include
                   
                     19 #include
                    
                      20 #include
                     
                       21 #include
                      
                        22 #include
                       
                         23 #include
                        
                          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 }