There is an N*M matrix with only 0s and 1s, (1 <= N,M <= 1000). An exact cover is a selection of rows such that every column has a 1 in exactly one of the selected rows.
Try to find out the selected rows.
InputThere are multiply test cases.
First line: two integers N, M;
The following N lines: Every line first comes an integer C(1 <= C <= 100), represents the number of 1s in this row, then comes C integers: the index of the columns whose value is 1 in this row.
OutputFirst output the number of rows in the selection, then output the index of the selected rows.
If there are multiply selections, you should just output any of them.
If there are no selection, just output "NO".
Sample Input
6 7 3 1 4 7 2 1 4 3 4 5 7 3 3 5 6 4 2 3 6 7 2 2 7
Sample Output
3 2 4 6
题意，从一个n*m的矩阵选若干行，使得每列在所选行中恰好有一个1。输入 第一行：两个整数N，M;
以下N行：每行首先出现一个整数C（1 <= C <= 100），表示该行中1的个数，然后是C个整数：该行中值为1的列的索引。
输出：首先输出选择中的行数，然后输出所选行的索引。
如果有多个选择，您应该只输出它们中的任何一个。
如果没有选择，只输出“NO”。
思路：精确覆盖问题用Dancing Links X 算法求解，详细情况见代码
代码：
1 #include <cstdio>
2 #include <fstream>
3 #include <algorithm>
4 #include <cmath>
5 #include <deque>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <cstring>
10 #include <map>
11 #include <stack>
12 #include <set>
13 #include <sstream>
14 #include <iostream>
15 #define mod 1000000007
16 #define eps 1e-6
17 #define ll long long
18 #define INF 0x3f3f3f3f
19 using namespace std;
20
21 struct{
22 int n,m;//n表示行数，m表是列数
23 int left[1001010],right[1001010],up[1001010],down[1001010],col[1001010],row[1001010];
24 // 左，右，上，下，列，行
25 int head[1010],ans[1010];
26 // 头，答案
27 int ansed,size;
28 // 计数，标识
29 void init(int _n,int _m)//初始化数据
30 {
31 n=_n;
32 m=_m;
33 //建立矩阵的第0行
34 for(int i=0;i<=m;i++)
35 {
36 up[i]=i;
37 down[i]=i;
38 left[i]=i-1;
39 right[i]=i+1;
40 col[i]=i;
41 row[i]=0;
42 }
43 left[0]=m;
44 right[m]=0;
45 size=m;
46 memset(head,-1,sizeof(head));
47 memset(ans,0,sizeof(ans));
48 ansed=0;
49 return ;
50 }
51 //插入数据
52 void insert(int r,int c)
53 {
54 size++;//矩阵中存入的数是size
55 down[size]=down[c];
56 up[size]=c;
57 up[down[c]]=size;
58 down[c]=size;
59 row[size]=r;
60 col[size]=c;
61 if(head[r]<0)//每一行存入第一个数时
62 {
63 head[r]=size;
64 left[size]=right[size]=size;
65 }
66 else
67 {
68 left[size]=head[r];
69 right[size]=right[head[r]];
70 left[right[head[r]]]=size;
71 right[head[r]]=size;
72 }
73 return ;
74 }
75 //删除数据的一列和每列对应的行
76 void delet(int c)
77 {
78 //删除一列
79 right[left[c]]=right[c];
80 left[right[c]]=left[c];
81 //删除行
82 for(int i=down[c];i!=c;i=down[i])//往下循环此列的每一个数
83 {
84 for(int j=right[i];j!=i;j=right[j])//i所在行往右循环每一个数
85 {
86 down[up[j]]=down[j];
87 up[down[j]]=up[j];
88 }
89 }
90 return ;
91 }
92 //恢复数据的一列和每列对应的行
93 void reback(int c)
94 {
95 //恢复行
96 for(int i=up[c];i!=c;i=up[i])//往上循环此列的每一个数
97 {
98 for(int j=left[c];j!=i;j=left[j])//i所在行往左循环每一个数
99 {
100 down[up[j]]=i;
101 up[down[j]]=i;
102 }
103 }
104 //恢复一列
105 right[left[c]]=c;
106 left[right[c]]=c;
107 return ;
108 }
109 //主循环
110 bool dancing(int dep)
111 {
112 if(right[0]==0)//如果Head.Right=Head，退出
113 {
114 ansed=dep;
115 return true;
116 }
117 int c=right[0];
118 delet(c);//删除上述步骤2的紫色方块
119 for(int i=down[c];i!=c;i=down[i])
120 {
121 ans[dep]=row[i];
122 //删除上述步骤3中的橙色方块
123 for(int j=right[i];j!=i;j=right[j])
124 {
125 delet(col[j]);
126 }
127 //模拟删除后的矩阵
128 if(dancing(dep+1))
129 {
130 return true;
131 }
132 //恢复被删除的数据
133 for(int j=left[i];j!=i;j=left[i])
134 {
135 reback(col[j]);
136 }
137 }
138 return false;
139 }
140 }dlx;
141 int main()
142 {
143 int n,m,p,k;
144 while(scanf("%d %d",&n,&m)!=EOF)
145 {
146 dlx.init(n,m);
147 for(int i=1;i<=n;i++)
148 {
149 scanf("%d",&p);
150 for(int j=1;j<=p;j++)
151 {
152 scanf("%d",&k);
153 //插入第i行第k列的数
154 dlx.insert(i,k);
155 }
156 }
157 //判断是否有结果
158 if(!dlx.dancing(0))
159 {
160 printf("NO\n");
161 }
162 else
163 {
164 printf("%d",dlx.ansed);
165 for(int i=0;i<dlx.ansed;i++)
166 {
167 printf(" %d",dlx.ans[i]);
168 }
169 printf("\n");
170 }
171 }
172 return 0;
173 }