|
|
  /**//*
 从昨天下午就开始搞，今天中午才搞定，Dancing Links 果然高深
神奇的双向环形十字链表······转的头晕了-_-||不过蛮有成就感的^v^
记录一下解题过程，先反反复复看了一遍Donald E.Knuth的论文，就开始攻hust 1017这道题目，
题目意思很明确：
给定一个由0和1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1。
论文中有详细解答，具体思路就是：
1. 任意选择一列c，然后删除它(这个删除并不是普通的把这一列删除，而是要将这一列中有1的格子所在的行全部删除)
2. 然后对这一列上有1的每一行进行枚举，当枚举到第i行时
该行上所有有1的列j全部删除(同上删除法)
3. 然后递归进入下一次，直到所有的列均被删除则有解
4. 恢复对j的删除
5. 恢复对c的删除
 */
#include <iostream>
using namespace std;
struct point  {
int L;
int R;
int U;
int D;
int Sum;
int x, y;
}p[ 1010 * 1010 ];
int n, m;
int i, j, k;
int map[1001][1001];
int sor[1001];
int flag;
int stack[1001], top;
int Num(int x, int y) {
return x * 1001 + y;
}
//删除c列
void CoverCol(int c) {
int i, j;
p[ p[ c ].R ].L = p[ c ].L;
p[ p[ c ].L ].R = p[ c ].R;
//删除c列中每个有1的行
i = c;
  for(i = p[i].D; i != c; i = p[i].D) {
j = i;
p[ p[i].y ].Sum --;
for(j = p[j].R; j != i; j = p[j].R) {
p[ p[j].D ].U = p[ j ].U;
p[ p[j].U ].D = p[ j ].D;
 }
}
}
//恢复c列
void Release(int c) {
int i, j;
p[ p[ c ].R ].L = c;
p[ p[ c ].L ].R = c;
//恢复c列中每个有1的行
i = c;
for(i = p[i].U; i != c; i = p[i].U) {
j = i;
p[ p[i].y ].Sum ++;
for(j = p[j].L; j != i; j = p[j].L) {
p[ p[j].D ].U = j;
p[ p[j].U ].D = j;
}
}
}
int dfs(int k) {
int i, j, l, m;
if(flag) return 1;
//得解输出
if(p[ 0 ].R == 0) {
printf("%d", top);
for(i = 0; i < top; i++)
printf(" %d", stack[i]);
puts("");
flag = 1;
return 1;
}
int c = 0; //每次取出没有被覆盖的并且1的个数最小的一列
int Min = INT_MAX;
i = c;
for(i = p[i].R; i ; i = p[i].R) {
if(p[ p[i].y ].Sum < Min) {
Min = p[ p[i].y ].Sum;
c = i;
}
}
//将这一列删除
CoverCol(c);
i = c;
//枚举c列中的每一行
for(i = p[i].D; i != c; i = p[i].D) {
//p[i].x 作为当前枚举的行，进栈
stack[ top++ ] = p[i].x;
j = i;
//对于该枚举的行，删除该行上1的格子所在的列
for(j = p[j].R; j != i; j = p[j].R) {
CoverCol(p[j].y);
}
if ( dfs(k+1) )
return 1;
//对于该枚举的行，恢复该行上1的格子所在的列
j = i;
for(j = p[j].L; j != i; j = p[j].L) {
Release(p[j].y);
}
top --;
}
//恢复c
Release(c);
return 0;
}
int main() {
int T = 0;
while(scanf("%d %d", &n, &m) != EOF) {
T ++;
for(i = 1; i <= n; i++) {
scanf("%d", &k);
for(j = 0; j < k; j++) {
scanf("%d", &sor[j]);
map[i][sor[j]] = T;
}
int lef = Num(i, sor[0]);
int rig = Num(i, sor[k-1]);
p[ lef ].L = rig;
p[ lef ].x = i;
p[ lef ].y = sor[0];
for(j = 1; j < k; j++) {
int cur = Num(i, sor[j]);
p[ Num(i, sor[j-1]) ].R = cur;
p[ cur ].L = Num(i, sor[j-1]);
p[ cur ].x = i;
p[ cur ].y = sor[j];
}
p[ rig ].R = lef;
}
p[0].R = 1;
for(i = 1; i <= m; i++) {
int No = Num(0, i);
if(i + 1 <= m)
p[ No ].R = Num(0, i+1);
else
p[ No ].R = 0;
p[ No ].L = Num(0, i-1);
p[ No ].x = 0;
p[ No ].y = i;
p[ No ].Sum = 0;
int last = No;
for(j = 1; j <= n; j++) {
if( map[j][i] == T ) {
p[ last ].Sum ++;
int now = Num(j, i);
p[ No ].D = now;
p[ now ].U = No;
No = now;
}
}
p[ No ].D = Num(0, i);
p[ Num(0, i) ].U = No;
if( !p[ last ].Sum ) {
printf("NO\n");
break;
}
}
if(i == m + 1) {
flag = 0;
top = 0;
dfs(0);
if(!flag)
puts("NO");
}
}
}
|