fzu 1686 神龙的难题 重复覆盖 DLX

缘起

【1】和【2】给出了DLX算法在精确覆盖问题中的应用. 下面给出DLX在重复覆盖问题中的应用. fzu 1686 神龙的难题

分析

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
这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,
魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使者艾米莉就是这样的一个人.她骑着她的坐骑——神龙米格拉一起消灭干扰人类生存的魔物,维护王国的安定.
艾米莉希望能够在损伤最小的前提下完成任务.每次战斗前,她都用时间停止魔法停住时间,
然后米格拉就可以发出火球烧死敌人.米格拉想知道,他如何以最快的速度消灭敌人,减轻艾米莉的负担.

Input
数据有多组,你要处理到EOF为止.每组数据第一行有两个数,n,m,(1<=n,m<=15)表示这次任务的地区范围. 
然后接下来有n行,每行m个整数,如为1表示该点有怪物,为0表示该点无怪物.然后接下一行有两个整数,n1,m1 (n1<=n,m1<=m)分别表示米格拉一次能攻击的行,列数(行列不能互换),假设米格拉一单位时间能发出一个火球,所有怪物都可一击必杀.

Output
输出一行,一个整数,表示米格拉消灭所有魔物的最短时间.

Sample Input
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
2 2
4 4 
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
2 2

Sample Output
4
1

限制
1s

其实舞蹈链算法困难的地方并不在模板, 而在于如何将一个问题转换为舞蹈链的精确覆盖亦或是重复覆盖.

本题的题意是

1
2
3
就是现在给出一个n*m的01矩阵
每次可以选择将一个n1*m1的矩形中的所有1变成0
问将所有的1变成0需要使用n1*m1的矩形至少多少次

其实舞蹈链本身并不难——本质就是在十字双向链表上进行dfs. 难在建模上.

关于舞蹈链模型建立我们可以再讲2个例子——虽然这两个问题目前已经没有题目可以提交了.

借助这两个例子，我们进一步理解如何将一个问题转换为舞蹈链.

问题1: 高手做题 (重复覆盖)

本例子大量借鉴 【4】

有n道题目, m位解题高手. 但是每个解题高手不是都能解答所有题目. 每位高手只会做其中的若干道题目. 问最少聘请几位高手才能保证每道题目都有高手能解决?

这个问题是典型的重复覆盖问题了. 所谓重复匹配问题即给你一个01矩阵. 要你选出若干行，要保证每一列都至少有一个1. 问最少需要多少行. 注意，精确匹配和重复匹配问法的不同. 精确匹配一般仅仅是要求一组可行解即可. 而重复匹配一般是求最优解.

那么重复匹配问题和精确匹配的不同点在哪里呢? 就在【3】中所说的”标识一列”中. 【3】中的标识一列的意思是将此列首先从舞蹈链中去掉. 然后将此列中所有元素所在行上的所有元素都从相应的垂直方向的链表（U/D）中移除. 但是对于重复覆盖问题，所谓的标识某列只能单纯的移除掉此列, 而不能再有后续动作了（在本文中. 我们依旧将这种操作对于重复覆盖问题叫做标识某列）——即不能将此列上所有元素所在行上的所有元素都从垂直方向的链表中移除. 为什么? 因为是重复覆盖——你不能阻止同一列中有多个1. 举个例子吧~ 还是这个高手做题的例子. 假如数据如下

1
2
3
4
5
4 4 // 4道题目, 4位高手
2 1 2 // 第1位高手会2道题目, 会第1道和第2道题目
1 4 // 第2位高手会1道题目, 会第4道题目
3 2 3 4  // 第3位高手会3道题目, 会第2道、第3道和第4道题目
2 1 3 // 第4位高手会2道题目, 会第1道和第3道题目

则将其转换为01矩阵

其中第i行是第i位高手的做题情况.

我们需要找最少的行，确保每一列至少有一个1. 和精确覆盖一样，先选择含1最少的列，这里选择的是第一列. 然后根据前面说的, 你只能将第一列移除掉而不能有任何后续动作了.即我们首先标识第一列. 然后选择第一列中的含有1的一行——比如选择第一行. 则该行的第二列也有1. 所以第二列可以去掉，即我们可以标识第二列. 则在我们标识了第一列和第二列之后，矩阵变为

图中的x意思是标识了此列（即移除了此列）. 注意，第四行第3列的1如果在精确匹配问题中将会在标识第1列的过程中被移除掉的. 但是本题是重复覆盖，所以不会移除——因为你不能阻止我选择第四行来贡献第三列的1嘛~ 纵使我第四行第一列的1和已经选择了的第一行第一列的1重复了（导致第一列有2个1，但是重复覆盖问题允许一列有多个1）

然后我们再选择第三列，则标识掉第三列. 然后选择第三列的第三行来共享第三列的那个1. 则第三行的所有1所在的列都要被标识掉. 即第四列就被标识掉了. 即矩阵变为

看到了没有? 出现了4个x，表明所有的列都有1了. 我们找到了一组可行解——1、3行（第二列有2个1）. 但是我们要求的是最少的行数. 所以并不能像精确匹配那样找到一组解就返回. 而要回溯然后找出全部解（整个过程中可以剪枝）然后求出最优的解（本题就是用的行数最少）.

开始回溯，回标第四列（本文标识动作的逆）. 然后选择第三列的第四行来贡献第三列的1（而不是选择第三列的第四行来贡献第三列的1）. 即

但是发现这样的话，将不能得到最优解——因为已经2行了，但是第四列还没有1出现（剪枝掉）. 所以要继续回溯. 即第一列的1不要第一行来贡献而是第四行来贡献第一列的1.即

则相应的第三列也被标识了（而不再是第二列）.

然后考虑第二列的1该由谁来贡献? 选择第一行, 则同上得不到最优解——已经2步了, 但是最后一列依旧没有1. 所以剪枝掉再回溯——选择第二列的第三行. 则需要标识掉第四, 即

所以我们得到了另一组可行解——(3,4).

综上，我们得到了精确匹配和重复匹配的区别

1
2
3
4
5
6
1. 重复覆盖问题一般是求解最优解的，不像精确覆盖找到一个解就算完事，因此重复覆盖需要遍历和考察所有的分
支，来找到最优的                   

2. 精确覆盖更能体现DLX的威力，因为在剪枝的时候，精确覆盖不仅对列剪枝，对行也进行了剪枝， 
而重复覆盖只对列进行剪枝（即精确匹配和重复匹配中"标识"这个动作的含义不一样），
要想提高重复覆盖的效率还需要自己写剪枝函数. 一般如果不剪枝的话, 会被T掉

关于第二点的剪枝函数. 我们这么考虑首先我们应该尽可能快一点求出一组解（例如上面的(1,3)）,如何快一点? 每次选择1较少的列进行标识. 一旦求出一组可行解, 则它就可以作为剪枝的依据. 而对于当前状态需要估计如果需要覆盖剩下的所有列的话，至少需要多少行. 这个剪枝函数暴力但是有效(具体代码参见本题的代码)

问题2: 伤脑筋的12块 (DLX精确匹配的经典应用)

所谓12块游戏是上面的8*8的骨牌拼图. 由12块5格骨牌组成. 中间留有2*2的空隙. 如何用程序得到一组可行解?

没错, 就是通过DLX精确匹配. 所以问题来了——如何将上面的骨牌游戏转换为精确匹配问题? 很简单.

72列矩阵. 1~12列是12种骨牌（每种骨牌恰好只能使用一次）. 后面60列是8*8棋盘挖去中间2*2空隙剩下的60个小方格（每个小方格只允许恰好一块骨牌占据）.

而每一行（据说有1568行）刻画的是一块骨牌在8*8移除2*2的棋盘上的放法. 例如第一行是1*5的骨牌（即上图黑色骨牌）的多种放法占据格子情况，占据了的话，矩阵就填1，否则填0. 而且在前12列找到相应的列填1表示当前使用的是某种骨牌. 所以这个矩阵就是一个01矩阵. 而一种合法的放法就是该矩阵的精确匹配问题（显然，前12列的精确匹配就决定了最后我们要选出12行）.

我们就可以施展DLX算法来解决给出一组可行解了.

问题2是很好的转精确匹配的思路!

好了, 说了这么多， 回到本题. 借助问题2的思路, 我们就很好转换神龙难题为重复匹配问题了.

只需要逐个考察n1*m1的矩阵的各种放法. 每种放法能消灭的1.

更确切的说——统计1的个数. 例如M个, 则转换后的01矩阵就是M列的. 然后行就是n1*m1的子矩阵的

(n-n1)*(m-m1) 种放法. 所以转换后的矩阵是 (n-n1)*(m-m1) 行, M列的.

对于每种放法，确定能消灭的1的位置. 则问题就变成一个裸的重复匹配问题了. 套重复覆盖模板即可.

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 300, maxm = 1000;
int N,M,m,a[20][20],n1,m1,tot, u[maxm],d[maxm], l[maxm], r[maxm],row[maxm], col[maxm], h[maxm], t, cnt[maxn],ans; // ans是最少行数 

void init()
{
	memset(h, 0, sizeof(h));
	for (int i = 0; i<=m; i++)
	{
		l[i+1]=i, r[i] = i+1, d[i]=u[i]=i, cnt[i] = 0; 
	}
	l[0] = m, r[m] = 0; 
	t = m+1;
}

void link(int i, int j) 
{
	cnt[j]++,row[t] = i,col[t] = j; 
	d[t] = d[j],u[t] = j,u[d[j]] = t,d[j] = t; 
	if (!h[i])
	{
		h[i]=l[t]=r[t]=t;
	}
	else 
	{
		l[t]=h[i], r[t]=r[h[i]], l[r[h[i]]]=t, r[h[i]]=t;
	}
	t++;
}

void remove(int c) // 和精确匹配不同, 这里仅仅是这一列上所有的元素（除了c之外）从这些元素所在的行上移除掉
{
	for (int i = d[c]; i!=c; i = d[i])
	{
		l[r[i]]=l[i],r[l[i]]=r[i];
	}
}

void resume(int c) 
{
	for (int i = u[c]; i!=c; i = u[i])
	{
		l[r[i]]=r[l[i]]=i;
	}
} 

bool v[maxn]; // 注意, v的维度是列数的最大,不是N,而是maxn,RE了一发

int g() // 根据当前的形式确定覆盖掉剩下所有的列最少需要多少行
{
	int ans = 0;
	memset(v, 0, sizeof(v));
	for (int i = r[0]; i; i = r[i]) // 剩下尚未覆盖的列
	{
		if (!v[i])
		{
			ans++;
			v[i] = true;
			for (int j = d[i]; j!=i; j=d[j])
			{
				for (int k = r[j]; k!=j; k = r[k])
				{
					v[col[k]] = true; // 从这里能看出此剪枝函数是相当粗糙的了(因为将所有能覆盖掉这一列的行的所有其他剩余元素能覆盖掉的列也消灭掉了),但是也很强力了~
				}
			}
		}
	}
	return ans;
}

void dance(int step) 
{
	if (!r[0]) // 得到一组可行解(所有的列都被覆盖了)
	{
		if (step<ans)
		{
			ans = step;
		}
		return;
	}
	if (step+g()>=ans) // 强力剪枝
	{
		return;
	}
	int _max = maxn, nxtCol;
	for (int i = r[0]; i; i = r[i]) 
	{
		if (_max>cnt[i])
		{
			nxtCol = i;
			_max = cnt[i];
		}
	} // 优先搜索含1的个数最少的列——为了能更快的找到一组可行解作为剪枝依据
	for (int i = d[nxtCol]; i!=nxtCol; i = d[i])  // 选定其中某一行,标识掉此行上所有元素所在列
	{
		remove(i); // 注意, i一定不会是nxtCol
		for (int j = r[i]; j!=i; j = r[j]) // 标识掉此行上所有元素所在列
		{
			remove(j); 
		}
		dance(step+1);
		for (int j = l[i]; j!=i; j = l[j])
		{
			resume(j); 
		}
		resume(i);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%d%d", &N,&M))
	{
		ans = 0x3f3f3f3f;
		m = 0; // m是1的个数, 即01矩阵的1的个数
		for (int i = 0; i<N; i++)
		{
			for (int j = 0; j<M; j++)
			{
				scanf("%d", a[i]+j);
				if (a[i][j])
				{
					m++;
					a[i][j]=m; // 将此处的1变为它是第几个1
				}
			}
		}
		init(); 
		scanf("%d%d", &n1, &m1);
		for (int i = 0; i<=N-n1; i++) // 枚举子矩阵的左上角(i,j),其实这里还是可以进一步降低复杂度的,毕竟达到了O(N^4),但是N较小, 就无所谓啦~
		{
			for (int j = 0; j<=M-m1; j++)
			{
				for (int x = i; x<i+n1; x++)
				{
					for (int y = j; y<j+m1; y++)
					{
						if (a[x][y]) // 说明 (x,y)处的这个1可以被左上角在(i,j)处的n1*m1这个矩形覆盖
						{
							link(i*(M-m1+1)+j+1,a[x][y]); // 则01矩阵的i*j+1行的第a[x][y]列是1
						}
					}
				}
			}
		}
		dance(0);
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 236kB
Length 2568
Lang GNU C++
Submitted 2019-09-16 16:35:31
Shared
RemoteRunId 906209

关于上面ac代码的进一步说明. 即99到111行的for循环中的进一步说明. 其实和【1】中的精确匹配模板还是写的不太一样的. 具体体现在【1】中（第81行到98行）是先remove(nxtCol); 然后再选择一行, 而这里是将remove(nxtCol)（这里是remove(i)）; 放到了循环里面. 而且这里的remove是将除了入参c之外的所有列上的元素都从这些元素所在行上给卸下来了. 即是下面这个样子（精确匹配是不存在这个问题的~）

那么上面代码102行将陷入死循环——将永远回不到i(即j永远不等于i)~ 那么不移除入参c的话会有问题吗? 不会, 因为remove的入参c一定不会是nxtCol，即不会是列标. 所以列标头是会从r[0]这一双向链表中移除掉的. 所以即便我们没有将入参c真正卸下来（不能卸下来的原因在于如果卸下来的话，102行的for将陷入死循环. 因为你把入参c卸下来了，c即102行的i，i能找到其他顶点，但是其他顶点将再也没法回到i, 就像上图那样, 会绕过c的）

最后，多说一句，注意上面代码的g函数. 它其实可以作为A*中的启发式函数. 真实代价函数不消说就是dance的入参step. 所以本题完全可以使用分支限界法（其实就是A*算法）. 代码就不写了~

参考

【1】https://yfsyfs.github.io/2019/09/15/%E6%B4%9B%E8%B0%B7-P4929-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E8%88%9E%E8%B9%88%E9%93%BE%EF%BC%88DLX%EF%BC%89-%E7%B2%BE%E7%A1%AE%E5%8C%B9%E9%85%8D/

【2】https://yfsyfs.github.io/2019/09/14/spoj-1771-NQUEEN-Yet-Another-N-Queen-Problem-DLX/

【3】https://yfsyfs.github.io/2019/09/14/%E8%88%9E%E8%B9%88%E9%93%BE%EF%BC%88dancing-links%EF%BC%89%E7%AE%97%E6%B3%95/

【4】https://blog.csdn.net/mu399/article/details/7627778