[ACM] POJ 3740 Easy Finding （DLX模板題）

[ACM] POJ 3740 Easy Finding （DLX模板題）

Easy Finding Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16178 Accepted: 4343

Description

Given a M×N matrix A. A_ij ∈ {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

Source

POJ Monthly Contest - 2009.08.23, MasterLuo

解題思路：

題意為由01組成的矩陣，問能不能挑出幾行使組成的新矩陣每列只有一個1.

套用Dlx模板，不過G++ 超時，C++勉強能過。

代碼：

#include 
#include 
using namespace std;
const int maxnode=5000;
const int maxm=310;
const int maxn=18;

struct DLX
{
    int n,m,size;
    int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
    int H[maxn];//行頭節點
    int S[maxm];//每列有多少個節點
    int ansd,ans[maxn];//如果有答案，則選了ansd行，具體是哪幾行放在ans[ ]數組裡面，ans[0~ansd-1];

    void init(int _n,int _m)
    {
        n=_n,m=_m;
        for(int 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;//編號，每列都有一個頭節點，編號1-m
        for(int i=1;i<=n;i++)
            H[i]=-1;//每一行的頭節點
    }

    void link(int r,int c)//第r行，第c列
    {
        ++S[Col[++size]=c];//第size個節點所在的列為c,當前列的節點數++
        Row[size]=r;//第size個節點行位置為r
        D[size]=D[c];//下面這四句頭插法（圖是倒著的？)
        U[D[c]]=size;
        U[size]=c;
        D[c]=size;
        if(H[r]<0)
            H[r]=L[size]=R[size]=size;
        else
        {
            R[size]=R[H[r]];
            L[R[H[r]]]=size;
            L[size]=H[r];
            R[H[r]]=size;
        }
    }

    void remove(int c)//刪除節點c，以及c上下節點所在的行,每次調用這個函數，都是從列頭節點開始向下刪除，這裡c也可以理解為第c列
    {                 //因為第c列的列頭節點編號為c
        L[R[c]]=L[c];
        R[L[c]]=R[c];
        for(int i=D[c];i!=c;i=D[i])
            for(int j=R[i];j!=i;j=R[j])
        {
            U[D[j]]=U[j];
            D[U[j]]=D[j];
            --S[Col[j]];
        }
    }

    void resume(int c)//恢復節點c,以及c上下節點所在的行(同上，也可以理解為從第c列的頭節點開始恢復
    {
        for(int i=U[c];i!=c;i=U[i])
            for(int j=L[i];j!=i;j=L[j])
            ++S[Col[U[D[j]]=D[U[j]]=j]]; //打這一行太糾結了 T T
        L[R[c]]=R[L[c]]=c;
    }

    bool dance(int d)//遞歸深度
    {
        if(R[0]==0)
        {
            ansd=d;
            return true;
        }
        int c=R[0];
        for(int i=R[0];i!=0;i=R[i])
            if(S[i]>num;
                if(num)
                    x.link(i,j);
            }
        }
        if(!x.dance(0))
            printf("It is impossible\n");
        else
            printf("Yes, I found it\n");
    }
    return 0;
}