POJ3740 Easy Finding 舞蹈链 DLX

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目

精确覆盖问题模板题

算法

DLX算法

学习DLX算法--传送门

代码

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=+,M=+;

struct X{

    int L,R,U,D,Col,Row;

}p[N*M];

int n,m;

int g[N][M],C[M],cnt=;

bool flag=;

void Delete(int k){

    p[p[k].R].L=p[k].L;

    p[p[k].L].R=p[k].R;

    for (int i=p[k].D;i!=k;i=p[i].D)

        for (int j=p[i].R;j!=i;j=p[j].R){

            C[p[j].Col]--;

            p[p[j].U].D=p[j].D;

            p[p[j].D].U=p[j].U;

        }

}

void Reset(int k){

    p[p[k].L].R=k;

    p[p[k].R].L=k;

    for (int i=p[k].U;i!=k;i=p[i].U)

        for (int j=p[i].L;j!=i;j=p[j].L){

            C[p[j].Col]++;

            p[p[j].U].D=j;

            p[p[j].D].U=j;

        }

}

bool DLX(){

    if (p[].R==)

        return true;

    int k=p[].R;

    for (int i=p[k].R;i!=;i=p[i].R)

        if (C[i]<C[k])

            k=i;

    Delete(k);

    for (int i=p[k].D;i!=k;i=p[i].D){

        for (int j=p[i].R;j!=i;j=p[j].R)

            Delete(p[j].Col);

        if (DLX())

            return true;

        for (int j=p[i].L;j!=i;j=p[j].L)

            Reset(p[j].Col);

    }

    Reset(k);

    return false;

}

int main(){

    while (~scanf("%d%d",&n,&m)){

        for (int i=;i<=n;i++)

            for (int j=;j<=m;j++)

                scanf("%d",&g[i][j]);

        memset(p,,sizeof p);

        memset(C,,sizeof C);

        for (int i=;i<=m;i++)

            p[i].L=i-,p[i].R=i+,p[i].U=p[i].D=i;

        p[].L=m,p[m].R=,cnt=m;

        for (int i=;i<=n;i++){

            int first=cnt+;

            for (int j=;j<=m;j++)

                if (g[i][j]){

                    cnt++;

                    p[cnt].L=cnt-;

                    p[cnt].R=cnt+;

                    p[cnt].D=j;

                    p[p[j].U].D=cnt;

                    p[cnt].U=p[j].U;

                    p[j].U=cnt;

                    C[p[cnt].Col=j]++;

                    p[cnt].Row=i;

                }

            if (cnt>=first)

                p[first].L=cnt,p[cnt].R=first;

        }

        if (DLX())

            puts("Yes, I found it");

        else

            puts("It is impossible");

    }

    return ;

}