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 ; }
补充:软件开发 , C++ ,