POJ 3740 DLX

題意：給你一個01矩陣，然後求是否存在選擇一些行，使得每一列的1的個數都為1。 思路：貌似樸素的DFS也可以，加點剪枝就可以過。這裡貼個DLX的模版。   這裡講的很詳細。

#include <set>  
#include <map>  
#include <stack>  
#include <cmath>  
#include <queue>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <iomanip>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair<int,int>  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
  
using namespace std;  
  
#define N 5555  
  
///DLX  
int L[N] , R[N] , D[N] , U[N] ,S[N] , C[N] ,st[N] ;//S[] 表示這一列的點數。C[] 表示這個點位於那一列。  
int n , m , num , head ;  
  
void insert(int col , int pos){//在這一列插入序號為pos的點  
    int now = col ;  
    while(D[now] != col) now = D[now] ;  
    D[now] = pos ;  
    D[pos] = col ;  
    U[pos] = now ;  
    U[col] = pos ;  
}  
  
void init(){  
    head = 0 ;  
    R[head] = 1 ;L[head] = m ;  
    for (int i = 1 ; i <= m ; i ++ ){//每一行的頭指針  
        if(i == 1)L[i] = head ;  
        else L[i] = i - 1 ;  
        if(i == m)R[i] = head ;  
        else R[i] = i + 1 ;  
        U[i] = i ;  
        D[i] = i ;  
        S[i] = 0 ;  
        C[i] = i ;  
    }  
    num = m ;//已經插入m個節點  
    int k ;  
    for (int i = 1 ; i <= n ; i ++ ){  
        mem(st ,0) ;  
        for (int j = 1 ; j <= m ; j ++ ){  
            scanf("%d",&k) ;  
            if(!k)continue ;  
            num ++ ;  
            insert(j , num) ;  
            if(st[0] == 0){//每行的第一個  
                L[num] = num ; R[num] = num ;  
            }else{  
                L[num] = st[st[0]] ;  
                R[num] = st[1] ;  
                R[st[st[0]]] = num ;  
                L[st[1]] = num ;  
            }  
            st[++st[0]] = num ;  
            C[num] = j ;  
            S[j] ++ ;  
        }  
    }  
}  
  
void remove(const 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[C[j]] ;  
        }  
    }  
}  
  
void resume(const int &c){//恢復  
    for (int i = U[c] ; i != c ; i = U[i]){  
        for (int j = L[i] ; j != i ; j = L[j]){  
            ++ S[C[j]] ;  
            U[D[j]] = j ;  
            D[U[j]] = j ;  
        }  
    }  
    L[R[c]] = c ;  
    R[L[c]] = c ;  
}  
  
int dfs(const int &k){  
    if(R[head] == head)return 1 ;  
    int MX = inf ,c ;  
    for (int t = R[head] ; t != head ; t = R[t]){//找出點最少的一列  
        if(S[t] < MX){  
            MX = S[t] ;  
            c = t ;  
        }  
    }  
    remove(c) ;  
    for (int i = D[c] ; i != c ; i = D[i]){  
        for (int j = R[i] ; j != i ; j = R[j]){  
            remove(C[j]) ;  
        }  
        if(dfs(k + 1))return 1 ;  
        for (int j = L[i] ; j != i ; j = L[j]){  
            resume(C[j]) ;  
        }  
    }  
    resume(c) ;  
    return 0 ;  
}  
int main() {  
    while(cin >> n >> m){  
        init() ;  
        if(dfs(0))puts("Yes, I found it") ;  
        else puts("It is impossible") ;  
    }  
    return 0 ;  
}