POJ 3740 Easy Finding题解

POJ 3740 Easy Finding

Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you
find some rows that let every cloumn contains and only contains one 1.

Input

There are multiple cases ended by EOF. Test case up to 500.The first line of input is M, N (M ≤ 16, N ≤ 300). The next M lines every line contains N integers separated by space.

Output

For each test case, if you could find it output “Yes, I found it”, otherwise output “It is impossible” per line.

Sample Input

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

Sample Output

Yes, I found it
It is impossible

这是用舞蹈链解决的一个精准覆盖问题的模板题

#include <cstdio>
#include <cstring>
const int M = 20*310+310;
int n,m,s;
int Up[M],Down[M],Left[M],Right[M];
int Col[M],Row[M];
int Head[M];
int S[M];
int ansR,ans[M];

void pre()
{
    for(int i=0;i<=m;i++)
    {
        Up[i]=i;
        Down[i]=i;
        Left[i]=i-1;
        Right[i]=i+1;
        Col[i]=i;
        Row[i]=0;
        S[i]=0;
    }
    Left[0]=m;
    Right[m]=0;
    s=m;
    for(int i=0;i<=n;i++)
    {
        Head[i]=-1;
        ans[i]=0;
    }
    ansR=0;
}

void Insert(int r,int c)
{
    s++;
    Down[s]=Down[c];
    Up[s]=c;
    Up[Down[c]]=s;
    Down[c]=s;

    Row[s]=r;
    Col[s]=c;
    S[c]++;
    if(Head[r]<0)
    {
        Head[r]=s;
        Right[s]=s;
        Left[s]=s;
    }
    else
    {
        Left[s]=Head[r];
        Right[s]=Right[Head[r]];
        Left[Right[Head[r]]]=s;
        Right[Head[r]]=s;
    }
}

void Remove(int c)
{
    Left[Right[c]]=Left[c];
    Right[Left[c]]=Right[c];
    for(int i=Down[c];i!=c;i=Down[i])
    {
        for(int j=Right[i];j!=i;j=Right[j])
        {
            Up[Down[j]]=Up[j];
            Down[Up[j]]=Down[j];
            --S[Col[j]];
        }
    }
}

void Resume(int c)
{
    for(int i=Up[c];i!=c;i=Up[i])
    {
        for(int j=Left[i];j!=i;j=Left[j])
        {
            Down[Up[j]]=j;
            Up[Down[j]]=j;
            ++S[Col[j]];
        }
    }
    Right[Left[c]]=c;
    Left[Right[c]]=c;
}

bool Dance(int Deep)
{
    if(Right[0]==0)
    {
        ansR=Deep;
        return true;
    }
    int c=Right[0];
    for(int i=Right[0];i!=0;i=Right[i])
        if(S[i]<S[c])c=i;
    Remove(c);
    for(int i=Down[c];i!=c;i=Down[i])
    {
        ans[Deep]=Row[i];
        for(int j=Right[i];j!=i;j=Right[j])
        {
            Remove(Col[j]);
        }
        if(Dance(Deep+1))return true;
        for(int j=Left[i];j!=i;j=Left[j])
            Resume(Col[j]);
    }
    Resume(c);
    return false;
}

int main()
{
    int t;
    while(~scanf("%d%d",&n,&m))
    {
        pre();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&t);
                if(t)
                {
                    Insert(i,j);
                }
            }
        }
        bool flag=true;
        for(int i=1;i<=m;i++)
        {
            if(S[i]==0)
            {
                flag=false;
                break;
            }
        }
        if(flag&&Dance(1))
        {
            printf("Yes, I found it\n");
        }
        else printf("It is impossible\n");
    }
    return 0;
}