|
|
  /**//*
 從昨天下午就開始搞，今天中午才搞定，Dancing Links 果然高深
神奇的雙向環(huán)形十字鏈表······轉的頭暈了-_-||不過蠻有成就感的^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的個數(shù)最小的一列
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");
}
}
}
|