【POJ 3740】 Easy Finding

时间：2022-05-05 17:58

【题目链接】

【算法】

Dancing Links算法解精确覆盖问题

详见这篇文章：

【代码】

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 10010

int n,m,i,j,val;

struct DancingLinks
{
        int n,m,size;
        int U[MAXN],D[MAXN],L[MAXN],R[MAXN],Row[MAXN],Col[MAXN];
        int H[MAXN],S[MAXN];
        inline void init(int _n,int _m)
        {
                n = _n;
                m = _m;
                for (i = 0; i <= m; i++)
                {
                        S[i] = 0;
                        U[i] = D[i] = i;
                        L[i] = i - 1;
                        R[i] = i + 1;
                }
                R[m] = 0; L[0] = m;
                size = m;
                for (i = 1; i <= n; i++) H[i] = -1;
        }
        inline void link(int r,int c)
        {
                size++;
                Row[size] = r;
                Col[size] = c;
                S[c]++;
                D[size] = D[c];
                U[D[c]] = size;
                U[size] = c; 
                D[c] = size;
                if (H[r] < 0) L[size] = R[size] = H[r] = size;
                else
                {
                        R[size] = R[H[r]];
                        L[R[H[r]]] = size;
                        L[size] = H[r];
                        R[H[r]] = size;
                }
        }
        inline void remove(int c)
        {
                int i,j;
                L[R[c]] = L[c];
                R[L[c]] = R[c];
                for (i = D[c]; i != c; i = D[i])
                {
                        for (j = R[i]; j != i; j = R[j])
                        {
                                U[D[j]] = U[j];
                                D[U[j]] = D[j];
                                S[Col[j]]--;    
                        }
                }
        }
        inline void resume(int c)
        {
                int i,j;
                for (i = D[c]; i != c; i = D[i])
                {
                        for (j = R[i]; j != i; j = R[j])
                        {
                                D[U[j]] = j;
                                U[D[j]] = j;
                                S[Col[j]]++;
                        }
                }        
                L[R[c]] = c;
                R[L[c]] = c;
        }
        inline bool solve()
        {
                int i,c;
                if (R[0] == 0) return true;
                c = R[0];
                for (i = R[0]; i; i = R[i])
                {
                        if (S[i] < S[c])
                                c = i; 
                }
                remove(c);
                for (i = D[c]; i != c; i = D[i])
                {
                        for (j = R[i]; j != i; j = R[j]) 
                                remove(Col[j]);
                        if (solve()) return true;
                        for (j = R[i]; j != i; j = R[j]) 
                                resume(Col[j]); 
                } 
                resume(c);
                return false;
        }
} DLX;

int main() 
{
        
        while (scanf("%d%d",&n,&m) != EOF)
        {
                DLX.init(n,m);
                for (i = 1; i <= n; i++)
                {
                        for (j = 1; j <= m; j++)
                        {
                                scanf("%d",&val);
                                if (val == 1) DLX.link(i,j);        
                        }        
                }        
                if (DLX.solve()) printf("Yes, I found it\n");
                else printf("It is impossible\n");
        }
        
        return 0;
    
}