【HUST】1017 Exact cover
13386 ワード
1 #include<cstdio>
2 #define INF 0x7FFFFFFF
3 #define MAXN 1000010
4 int n, m, size;
5 int L[MAXN], R[MAXN], U[MAXN], D[MAXN], H[MAXN];
6 int S[MAXN], C[MAXN], X[MAXN], Q[MAXN];
7 void Init() {
8 int i;
9 for (i = 0; i <= m; i++) {
10 S[i] = 0;
11 L[i + 1] = i;
12 R[i] = i + 1;
13 U[i] = D[i] = i;
14 }
15 R[m] = 0;
16 size = m + 1;
17 }
18 void Remove(int c) {
19 int i, j;
20 R[L[c]] = R[c];
21 L[R[c]] = L[c];
22 for (i = D[c]; i != c; i = D[i]) {
23 for (j = R[i]; j != i; j = R[j]) {
24 D[U[j]] = D[j];
25 U[D[j]] = U[j];
26 S[C[j]]--;
27 }
28 }
29 }
30 void Resume(int c) {
31 int i, j;
32 R[L[c]] = c;
33 L[R[c]] = c;
34 for (i = D[c]; i != c; i = D[i]) {
35 for (j = R[i]; j != i; j = R[j]) {
36 U[D[j]] = j;
37 D[U[j]] = j;
38 S[C[j]]++;
39 }
40 }
41 }
42 void Link(int r, int c) {
43 S[c]++;
44 D[size] = D[c];
45 U[size] = c;
46 U[D[c]] = size;
47 D[c] = size;
48 if (H[r] < 0)
49 H[r] = L[size] = R[size] = size;
50 else {
51 L[size] = H[r];
52 R[size] = R[H[r]];
53 L[R[H[r]]] = size;
54 R[H[r]] = size;
55 }
56 C[size] = c;
57 X[size++] = r;
58 }
59 bool Dance(int now) {
60 int i, j, c, temp;
61 if (R[0] == 0) {
62 printf("%d", now);
63 for (i = 0; i < now; i++)
64 printf(" %d", X[Q[i]]);
65 putchar('
');
66 return true;
67 }
68 for (temp = INF, i = R[0]; i; i = R[i]) {
69 if (S[i] < temp) {
70 c = i;
71 temp = S[i];
72 }
73 }
74 Remove(c);
75 for (i = D[c]; i != c; i = D[i]) {
76 Q[now] = i;
77 for (j = R[i]; j != i; j = R[j])
78 Remove(C[j]);
79 if (Dance(now + 1))
80 return true;
81 for (j = L[i]; j != i; j = L[j])
82 Resume(C[j]);
83 }
84 Resume(c);
85 return false;
86 }
87 int main() {
88 int i, j, k;
89 while (~scanf("%d%d", &n, &m)) {
90 Init();
91 for (i = 1; i <= n; i++) {
92 H[i] = -1;
93 scanf("%d", &k);
94 while (k--) {
95 scanf("%d", &j);
96 Link(i, j);
97 }
98 }
99 if (!Dance(0))
100 puts("NO");
101 }
102 return 0;
103 }