题目链接:http://poj.org/problem?id=3740
题意： 是否从0,1矩阵中选出若干行，使得新的矩阵每一列有且仅有一个1？
原矩阵N*M $ 1<= N <= 16 $ , $ 1 <= M <= 300$
解法1：由于行数不多，二进制枚举选出的行数，时间复杂度为O((1<<16)*K), 其中K即为判断选出的行数是否存在相同的列中有重复的1；
优化：将1状压即可，这样300的列值，压缩在int的32位中，使得列数“好像”小于10了；这样每次只需要 一个数 进行与运算，即可判断32个列是否有重复的1；使得K <= 10;
并且在选中一列和删除一列时， 两次 xor操作就可复原~~
47ms ~~
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const int bit = ;
const int L = ;
int n, m, x[][L], g[L], w[L];
bool check(int *x, int *w)
{
for(int i = ; i < L; i++){
if(x[i] & w[i]) return true;
}
return false;
}
bool dfs(int p)
{
int flag = ;
for(int i = ; i < L && flag; i++) if(g[i] != w[i]) flag = ;
if(flag) return true;
if(p == n) return false;
if(check(x[p], w)) return dfs(p + ); // 判断是否当前的列与之前选中的列有重复的1 for(int i = ; i < L; i++) w[i] ^= x[p][i];
if(dfs(p+)) return true;
for(int i = ; i < L; i++) w[i] ^= x[p][i]; // 不选当前的列
return dfs(p+);
}
int main()
{
char a;
while( scanf("%d%d", &n, &m) == ){
memset(x, , sizeof(x));
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
a = getchar();
while (!isdigit(a)) a = getchar();
if (a == '') x[i][j/bit] |= << j%bit;
}
}
memset(w, , sizeof(w));
memset(g, , sizeof(g));
for(int i = ; i < m; i++) g[i/bit] |= << i%bit; if(dfs()) puts("Yes, I found it");
else puts("It is impossible");
}
}
解法2： DLX模板题，初学DLX，下面写下理解：
在DLX中搞清楚几个函数的含义，以及删除和恢复列操作的含义基本上理解了DLX 的模板了；
C[i] 表示每个有效节点所在的列， S[i] 表示每一列有效节点的个数，H[i] 表示每一列最右边有效节点的的标号；
L[i], R[i], U[i], D[i] 分别表示有效节点 i 上下左右节点的标号；
其中U[c] （c为列的标号） 表示列c中最下面的有效节点的标号， D[c] （c为列的标号）表示列c中最上面的有效节点的标号；
并且在删除和恢复一列时，循环遍历的是该列中的每一个节点； 这和选中一列，之后删除/恢复 行不同， 删除/恢复 行并没有包括起点（起点在列中操作了）；
具体的DLX思路： 选出S中最小的列c， 删除列c中所有的有效节点所在的行，之后枚举选出的是哪行；再删除该行所有有效节点所在的列；递归求解即可；
63ms ... 进竟然没有压缩枚举快，，写挫了
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = ;
int tot, head, n, m;
int C[maxn], S[maxn], H[maxn];
int U[maxn], D[maxn], L[maxn], R[maxn];
inline void add_link(int i, int j)
{
C[++tot] = j;
S[j]++; D[tot] = j;
U[tot] = U[j];
D[U[tot]] = tot;
U[D[tot]] = tot;//U[j]表示第j列最下面节点标号; if(H[i]) L[tot] = H[i], R[tot] = R[H[i]]; // H[i]是第i行最右边的节点标号
else R[tot] = L[tot] = tot; R[L[tot]] = tot;
L[R[tot]] = tot;
H[i] = tot;
} void Remove(int c)
{
R[L[c]] = R[c]; L[R[c]] = L[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(int c)
{
for(int i = U[c]; i != c; i = U[i]){
for(int j = L[i]; j != i; j = L[j]){
U[D[j]] = j;
D[U[j]] = j;
S[C[j]]++;
}
}
R[L[c]] = c; L[R[c]] = c;
}
bool DLX()
{
if(R[head] == head) return true;
int c, mn = inf;
for(int i = R[head]; i != head; i = R[i]) if(mn > S[i]) c = i, mn = S[i]; 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(DLX()) return true;
for(int j = L[i]; j != i; j = L[j]) Resume(C[j]);
}
Resume(c); return false;
}
int main()
{
while( scanf("%d%d", &n, &m) == ){
tot = m; head = ;
for(int i = ; i <= m; i++){
C[i] = U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
L[] = m, R[m] = ; char x;
for(int i = ; i <= n; i++){
H[i] = ;
for(int j = ; j <= m; j++){
x = getchar();
while (!isdigit(x)) x = getchar();
if (x == '') add_link(i, j);
}
}
if(DLX()) puts("Yes, I found it");
else puts("It is impossible");
}
}