题意：M行N列，各元素值要么是0，要么是1，问是否可以取出其中的一些行，使取出的行组合中每列有且仅有一个1。
题目链接：http://poj.org/problem?id=3740
——>>2014.10.30 再次更新
DLX 舞蹈链模板题。。
#include <cstdio>
#include <cstring>const int MAXM = 16 + 10;
const int MAXN = 300 + 10;
const int MAXNODE = MAXM * MAXN;struct DLX
{int sz;int H[MAXM], S[MAXN];int row[MAXNODE], col[MAXNODE];int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];void Init(int n){for (int i = 0; i <= n; ++i){U[i] = D[i] = i;L[i] = i - 1;R[i] = i + 1;}L[0] = n;R[n] = 0;sz = n + 1;memset(S, 0, sizeof(S));memset(H, -1, sizeof(H));}void Link(const int& r, const int& c){row[sz] = r;col[sz] = c;D[sz] = D[c];U[D[c]] = sz;D[c] = sz;U[sz] = c;if (H[r] == -1){H[r] = L[sz] = R[sz] = sz;}else{R[sz] = R[H[r]];L[R[H[r]]] = sz;R[H[r]] = sz;L[sz] = H[r];}S[c]++;sz++;}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[col[j]]--;}}}void Restore(const int& c){for (int i = U[c]; i != c; i = U[i]){for (int j = L[i]; j != i; j = L[j]){S[col[j]]++;U[D[j]] = j;D[U[j]] = j;}}L[R[c]] = c;R[L[c]] = c;}bool Dfs(){if (R[0] == 0){return true;}int c = R[0];for (int i = R[0]; i != 0; i = R[i]){if (S[i] < S[c]){c = i;}}Remove(c);for (int i = D[c]; i != c; i = D[i]){for (int j = R[i]; j != i; j = R[j]){Remove(col[j]);}if (Dfs()) return true;for (int j = L[i]; j != i; j = L[j]){Restore(col[j]);}}Restore(c);return false;}bool Solve(){return Dfs();}} dlx;int M, N;void Read()
{char ch;dlx.Init(N);for (int i = 1; i <= M; ++i){for (int j = 1; j <= N; ++j){getchar();ch = getchar();if (ch == '1'){dlx.Link(i, j);}}}
}void Solve()
{dlx.Solve() ? puts("Yes, I found it") : puts("It is impossible");
}int main()
{while (scanf("%d%d", &M, &N) != EOF){Read();Solve();}return 0;
}
——>>寒假时刷这题费了超大精力，现在再刷一次，理解起来快多了。
思想：用位运算来加速。
row[i]表示第i行的二进制移位编号，第i行就将1左移i位。
col[i]表示第j列在哪些行的值为1，哪些行的值为0。
dfs(int cur, int push, int pop)表示目前考查到了第cur列，push表示已经选出来的行，pop表示已经放弃的行。
if(ok) return 0;不要没错，但是不要浪费时间，如果说有x行都满足在第cur列的要求，第一行dfs已经使ok = 1了，若不要上述的这个判断，那么剩下的x-1行都来一次dfs，费时。
if(push&pop) return 0;前面放入push的行只是满足了当时的cur列要求，并不能保证现在的cur列是否满足要求。
dfs(cur + 1, push | row[i], pop | (row[i]^col[cur]));这里没有修改push和pop的值，所以回溯也不用修改push和pop的值。
好题，好题～
#include <cstdio>
#include <cstring>using namespace std;const int maxr = 16;
const int maxc = 300;
int M, N, row[maxr], col[maxc], MAP[maxr][maxc];
bool ok;void dfs(int cur, int push, int pop)
{if(ok || (push&pop)) return;if(cur == N){ok = 1;return;}for(int i = 0; i < M; i++){int temp = row[i] & col[cur];if(temp && !(row[i]&pop)){dfs(cur + 1, push | row[i], pop | (row[i]^col[cur]));}}
}int main()
{int i, j;for(i = 0; i < maxr; i++) row[i] = 1<<i;while(scanf("%d%d", &M, &N) == 2){memset(col, 0, sizeof(col));for(i = 0; i < M; i++)for(j = 0; j < N; j++){scanf("%d", &MAP[i][j]);if(MAP[i][j]) col[j] |= row[i];}ok = 0;dfs(0, 0, 0);if(ok)printf("Yes, I found it\n");elseprintf("It is impossible\n");}return 0;
}