hust - 1017 - Exact cover（精确覆盖DLX)

题意：N行M列的0 1矩阵(1 <= N,M <= 1000)，求选出其中的一些行，使得选出的这些行每列有且仅有一个1，输出选出行的行号，无解输出"NO"。

题目链接：http://acm.hust.edu.cn/problem/show/1017

——>>DLX 练手。。

#include <cstdio>
#include <cstring>const int MAXN = 1000 + 10;
const int MAXNODE = MAXN * MAXN;struct DLX
{int sz;int H[MAXN], S[MAXN];int row[MAXNODE], col[MAXNODE];int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];int ret[MAXN], cnt;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;cnt = 0;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(int cur){if (R[0] == 0){cnt = cur;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]){ret[cur] = row[i];for (int j = R[i]; j != i; j = R[j]){Remove(col[j]);}if (Dfs(cur + 1)) return true;for (int j = L[i]; j != i; j = L[j]){Restore(col[j]);}}Restore(c);return false;}void Solve(){if (!Dfs(0)){puts("NO");}else{printf("%d", cnt);for (int i = 0; i < cnt; ++i){printf(" %d", ret[i]);}puts("");}}
} dlx;int N, M;void Read()
{int cnt, c;dlx.Init(M);for (int i = 1; i <= N; ++i){scanf("%d", &cnt);while (cnt--){scanf("%d", &c);dlx.Link(i, c);}}
}int main()
{while (scanf("%d%d", &N, &M) != EOF){Read();dlx.Solve();}return 0;
}