[Hust1017 Exact cover]【DLX】【精确覆盖例题】

【题目链接】http://acm.hust.edu.cn/thanks/problem.php?id=1017

【题目大意】

给定一个M*N的矩阵，上面只有1和0。其中M,N<=1000。

并且每一行的1的数量<=100。

让你取一些行，使得每一列恰好有一个1。

【算法分析】

这个吓人的规模。。。没错。。。就是搜索。

Dancing Link + Algorithm X

【其它】

很寂寞。时限15秒，我跑了4秒。第一名跑了120+MS。。。很好很沙茶。

【CODE】

C++ CODE   :Hust1017 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105 #include #include #include const int N=1005;
int m,n,dep,tot;
int Sum[N];
int L[N],R[N],U[N][N],D[N][N];
int a[N][105];
int ansL[N];
int Sx[N*N/10],Sy[N*N/10];

void init(){
int i,j,x;
for (j=0;j<=n;j++){
D[0][j]=0;
U[0][j]=0;
}
memset(Sum,0,sizeof(Sum));
for (i=1;i<=m;i++){
scanf("%d",&a[i][0]);
for (j=1;j<=a[i][0];j++){
scanf("%d",&x);
a[i][j]=x;
Sum[x]++;
D[i][x]=0;
U[i][x]=U[0][x];
U[D[i][x]][x]=i;
D[U[i][x]][x]=i;
}
}
for (i=0;i for (i=1;i<=n;i++) L[i]=i-1; L[0]=n;
}

void Delete(int Col){
int i,j,tmp=tot,next;
for (i=D[0][Col];i;i=next){
next=D[i][Col];
for (j=1;j<=a[i][0];j++){
int &x=a[i][j];
Sum[x]–;
U[D[i][x]][x]=U[i][x];
D[U[i][x]][x]=D[i][x];
tot++;
Sx[tot]=i;
Sy[tot]=x;
}
}
L[R[Col]]=L[Col];
R[L[Col]]=R[Col];
}

void Recover(int k){
while (tot!=k){
int &i=Sx[tot],&x=Sy[tot];
Sum[x]++;
U[D[i][x]][x]=i;
D[U[i][x]][x]=i;
tot–;
}
}

bool dfs(){
if (!R[0]) return true;
int i,j,Min=0x7FFFFFFF,Mini,tmp;
for (i=R[0];i;i=R[i])
if (Sum[i] Min=Sum[i];
Mini=i;
}
if (Min==0) return false;
for (i=D[0][Mini];i;i=D[i][Mini]){
ansL[dep++]=i;
tmp=tot;
for (j=1;j<=a[i][0];j++)
Delete (a[i][j]);
if (dfs()) return true;
dep–;
for (j=a[i][0];j>=1;j–){
int &Col=a[i][j];
L[R[Col]]=Col;
R[L[Col]]=Col;
}
Recover(tmp);
}
return false;
}

void output(){
printf("%d",dep-1);
for (int i=1;i puts("");
}

int main(){
while (1){
if (scanf("%d%d",&m,&n)==EOF) break;
init();
dep=1;
tot=0;
if (dfs()) output();
else puts("NO");
}
return 0;
}