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