首页 > 代码库 > 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 }
View Code

 

POJ 3740 Easy Finding DLX