POJ 3740 DLX 精确覆盖模板题 - c++编程基础

Easy Finding

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 15209		Accepted: 4028

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

Sample Output

Yes, I found it
It is impossible
模板题，不解释，直接贴代码;
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-8 20:57:41
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; struct DLX{ const static int maxn=7000; int L[maxn],R[maxn],U[maxn],D[maxn]; int ans[maxn],size,cnt,row[maxn],col[maxn],S[maxn],H[maxn]; void del(int 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 add(int c){ R[L[c]]=L[R[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]]; } void init(int m){ for(int i=0;i<=m;i++){ S[i]=0; L[i]=i-1; R[i]=i+1; U[i]=D[i]=i; } L[0]=m;R[m]=0; size=m+1; memset(H,-1,sizeof(H)); } void link(int x,int y){ ++S[col[size]=y]; row[size]=x; D[size]=D[y]; U[D[y]]=size; U[size]=y; D[y]=size; if(H[x]<0)H[x]=L[size]=R[size]=size; else { R[size]=R[H[x]]; L[R[H[x]]]=size; L[size]=H[x]; R[H[x]]=size; } size++; } bool dfs(int k){ if(!R[0]){ cnt=k; return 1; } int c=R[0];for(int i=R[0];i;i=R[i])if(S[c]>S[i])c=i; del(c); for(int i=D[c];i!=c;i=D[i]){ for(int j=R[i];j!=i;j=R[j])del(col[j]); ans[k]=row[i]; if(dfs(k+1))return true; for(int j=L[i];j!=i;j=L[j])add(col[j]); } add(c); return 0; } }dlx; int n,m; int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); while(cin>>n>>m){ int i,j,k; dlx.init(m); for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ scanf("%d",&k); if(k==1) dlx.link(i,j); } } if(dlx.dfs(0)) puts("Yes, I found it"); else puts("It is impossible"); } return 0; }