mydcwfy's Blog

舞蹈链（DLX）

Posted on
Symbols count in article: 9.8k Reading time ≈ 21 mins.

题型有两种：精确覆盖与重复覆盖。

1. 废话

首先，它有几个名字：DLX,Dancing Links,十字链表，舞蹈链。

然后，它是一种数据结构。

精确覆盖是指每一列恰好有一个 1。

重复覆盖是指每一列至少有一个 1。

它解决的问题，一般矩阵规模较大，但 1 的个数较少。

可以通过题目来理解。

题目传送门 Luogu

题目传送门 AcWing

2. 精确覆盖问题

1）如何存储矩阵

使用十字链表。

对于每一个 1，都建立一个节点。

2）初始化

每一个节点的上下左右都连向该方向的最近链表。（如果没有，就循环找）。

实际使用时，可以按照一行一行的处理。

同时，对于最前面，我们建立一个哨兵，全为 1。

上面的操作就是初始化。

3）插入一行

建立当前行的前面和后面，插入时，直接选择即可。

这里有些难理解，我们结合代码讲。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void add(int &hh,int &tt,int x,int y)
{
    l(idx)=hh,r(idx)=tt,r(hh)=idx,l(tt)=idx;
    d(idx)=d(y),u(idx)=y,u(d(y))=idx,d(y)=idx;
    col(idx)=y;row(idx)=x;
    tt=idx++;s[y]++;
}

for (int i=1,x;i<=n;++i)
    {
        int hh=idx,tt=idx;
        for (int j=1;j<=m;++j)
        {
            scanf("%d",&x);
            if (x) add(hh,tt,i,j);
        }
    }
//in main()

最开始时，第一个点的右边和左边都是当前本身，所以初始时都是 idx,更新时直接将 tt 赋值为 idx，就串成了一个循环链表。

4）搜索

在 dfs 的过程中，从未选择的行中任意选择一行，搜索一行。

剪枝：

  1. 比较明显，直接选择包含 1 最少的一列选择一行。
  2. 在选择一列后，将该列删除。
  3. 在选择一行后，将该行包含 1 的列全部删除。

这里，我们发现，需要 2 个函数：删除一列和恢复一列。

5）删除一列

对于哨兵，可以直接删除。

但是，由于要满足”精确覆盖“，我们要将包含该列的行全部删掉。

6）恢复一列

7）Code

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e4+10;

struct DLX{
    int l,r,u,d;
    int row,col;
    #define l(i) a[i].l
    #define r(i) a[i].r
    #define u(i) a[i].u
    #define d(i) a[i].d
    #define row(i) a[i].row
    #define col(i) a[i].col
}a[N];

int s[N];
int idx;
int ans[N],top;
int n,m;

void init()
{
    for (int i=0;i<=m;++i)
    {
        l(i)=i-1;r(i)=i+1;
        u(i)=d(i)=i;
    }
    l(0)=m;r(m)=0;
    idx=m+1;
}

void add(int &hh,int &tt,int x,int y)
{
    l(idx)=hh,r(idx)=tt,r(hh)=idx,l(tt)=idx;
    d(idx)=d(y),u(idx)=y,u(d(y))=idx,d(y)=idx;
    col(idx)=y;row(idx)=x;
    tt=idx++;s[y]++;
}

void remove(int p)
{
    r(l(p))=r(p),l(r(p))=l(p);

    for (int i=d(p);i!=p;i=d(i))
        for (int j=r(i);j!=i;j=r(j))
        {
            s[col(j)]--;
            u(d(j))=u(j),d(u(j))=d(j);
        }
}

void resume(int p)
{
    for (int i=u(p);i!=p;i=u(i))
        for (int j=l(i);j!=i;j=l(j))
        {
            s[col(j)]++;
            u(d(j))=j,d(u(j))=j;
        }
    r(l(p))=p,l(r(p))=p;
}

bool dfs()
{
    if (!r(0)) return true;
    int p=r(0);
    for (int i=r(0);i;i=r(i))
        if (s[i]<=s[p]) p=i;
    if (!p) return false;

    remove(p);
    for (int i=d(p);i!=p;i=d(i))
    {
        ans[++top]=row(i);
        for (int j=r(i);j!=i;j=r(j)) remove(col(j));
        if (dfs()) return true;
        for (int j=l(i);j!=i;j=l(j)) resume(col(j));
        top--;
    }
    resume(p);
    return false;
}

int main()
{
    scanf("%d %d",&n,&m);
    init();
    for (int i=1,x;i<=n;++i)
    {
        int hh=idx,tt=idx;
        for (int j=1;j<=m;++j)
        {
            scanf("%d",&x);
            if (x) add(hh,tt,i,j);
        }
    }

    if (dfs())
    {
        for (int i=1;i<=top;++i) printf("%d ",ans[i]);
        puts("");
    }
    else puts("No Solution!");
    return 0;
}

3. 例题

做 Dancing Links 的题，做法如下：

  1. 首先将题目的选择设为行。
  2. 然后将题目的限制设为列。
  3. 使用模板。

T1：数独2

题目传送门 AcWing

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
struct DLX{
    int l, r, u, d, row, col;
}a[N];
struct Option{
    int row, col, k;
}opt[N];
int n, m = 1024, sz[1025], idx, ans[N], top;
char s[21][21];

void init()
{
    for (int i = 1; i <= m; ++ i)
    {
        a[i] = {i - 1, i + 1, i, i, 0, i};
        sz[i] = 0;
    }
    a[0].l = m, a[0].r = 1, a[m].r = 0, idx = m + 1;
}

void add(int &hh, int &tt, int x, int y)
{
    a[idx] = {hh, tt, y, a[y].d, x, y};
    a[a[y].d].u = idx, a[y].d = idx;
    a[hh].r = a[tt].l = idx;
    sz[y] ++, tt = idx ++;
}

inline int get(int x, int y){return x * 16 + y;}

void remove(int p)
{
    a[a[p].r].l = a[p].l, a[a[p].l].r = a[p].r;
    for (int i = a[p].d; i != p; i = a[i].d)
        for (int j = a[i].r; j != i; j = a[j].r)
        {
            sz[a[j].col] --;
            a[a[j].d].u = a[j].u, a[a[j].u].d = a[j].d;
        }
}

void resume(int p)
{
    for (int i = a[p].u; i != p; i = a[i].u)
        for (int j = a[i].l; j != i; j = a[j].l)
        {
            sz[a[j].col] ++;
            a[a[j].d].u = a[a[j].u].d = j;
        }
    a[a[p].l].r = a[a[p].r].l = p;
}

bool dfs()
{
    if (!a[0].r) return true;
    int p = a[0].r;
    for (int i = a[p].r; i; i = a[i].r)
        if (sz[i] < sz[p]) p = i;
    remove(p);
    top ++;
    for (int i = a[p].d; i != p; i = a[i].d)
    {
        ans[top] = a[i].row;
        for (int j = a[i].r; j != i; j = a[j].r) remove(a[j].col);
        if (dfs()) return true;
        for (int j = a[i].l; j != i; j = a[j].l) resume(a[j].col);
    }
    resume(p);
    top --;
    return false;
}

int main()
{
    int t = 0;
    while (~scanf("%s", s[1] + 1))
    {
        if (t) cout << endl;
        n = top = 0, init();
        for (int i = 2; i <= 16; ++ i) scanf("%s", s[i] + 1);
        for (int i = 1; i <= 16; ++ i)
            for (int j = 1; j <= 16; ++ j)
            {
                int x, y;
                if (s[i][j] == '-') x = 0, y = 15;
                else x = y = s[i][j] - 'A';
                for (int k = x; k <= y; ++ k)
                {
                    opt[++ n] = {i, j, k};
                    int hh = idx, tt = idx;
                    add(hh, tt, n, 256 * 0 + get(i - 1, j - 1) + 1);
                    add(hh, tt, n, 256 * 1 + get(i - 1, k) + 1);
                    add(hh, tt, n, 256 * 2 + get(j - 1, k) + 1);
                    add(hh, tt, n, 256 * 3 + get((i - 1) / 4 * 4 + (j - 1) / 4, k) + 1);
                }
            }
        dfs();
        // cout << dfs() << ' ' << top << endl;
        for (int i = 1; i <= top; ++ i)
        {
            auto &op = opt[ans[i]];
            s[op.row][op.col] = op.k + 'A';
        }
        for (int i = 1; i <= 16; ++ i) cout << s[i] + 1 << endl;
        t = 1;
    }
    return 0;
}

T2：[NOI2005]智慧珠游戏

题目传送门 Luogu

题目传送门 AcWing

将每一种摆法的旋转、平移的所有方法，都做成一个行，然后将每一个格子、每一种方法都做成列。

代码比较繁琐，但是思路不太难。

4. 重复覆盖问题

题目传送门 AcWing

与精确覆盖问题对比。

重复覆盖问题的规模较小，而精确覆盖问题的规模较大。

重复覆盖问题的答案较小，而精确覆盖问题的 1 个数较小。

为什么答案要求要比较小呢？

因为使用了 IDA* （迭代加深）。

算法流程如下：

  1. 选择一个行数最少的列

  2. 枚举当前列是 1 的行。

  3. 枚举当前行，递归。

对比精确覆盖问题，我们发现有不同。

于是，这个就会慢很多。

我们又有一个武器：IDA*。

加上这样一个句： if (k+h()>depth) return false;

这样，我们应该考虑怎样构造 h()。

请注意，我们要保证 $h()\leq ans$。

遍历所有未被覆盖的列，选择当前列的所有行，但是计数只记一行。

这样，我们其实选择了更多，所以答案不可能更大。

上代码。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=(int)1e4+10;

struct DLX{
    int l,r,u,d,row,col;
    #define l(i) a[i].l
    #define r(i) a[i].r
    #define u(i) a[i].u
    #define d(i) a[i].d
    #define col(i) a[i].col
    #define row(i) a[i].row
}a[N];

int idx,n,m,s[105],ans[105];
bool st[105];

void init()
{
    for (int i=0;i<=m;++i)
    {
        l(i)=i-1,r(i)=i+1;
        col(i)=u(i)=d(i)=i;
        s[i]=0;
    }
    l(0)=m,r(m)=0;
    idx=m+1;
}

void add(int &hh,int &tt,int x,int y)
{
    a[idx]=(DLX){hh,tt,y,d(y),x,y};
    u(d(y))=idx;d(y)=idx;s[y]++;
    l(tt)=r(hh)=idx;

    tt=idx++;
}

void remove(int p)
{
    for (int i=d(p);i!=p;i=d(i))
    {
        l(r(i))=l(i),r(l(i))=r(i);
    }
}

void resume(int p)
{
    for (int i=u(p);i!=p;i=u(i))
    {
        l(r(i))=r(l(i))=i;
    }
}

int h()
{
    int res=0;
    memset(st,0,sizeof st);
    for (int i=r(0);i;i=r(i))
    {
        if (st[i]) continue;
        st[i]=true;res++;
        for (int j=d(i);j!=i;j=d(j))
            for (int k=r(j);k!=j;k=r(k)) st[col(k)]=true;
    }
    return res;
}

bool dfs(int k,int depth)
{
    if (k+h()>depth) return false;
    if (!r(0)) return true;
    int p=r(0);
    for (int i=r(0);i;i=r(i))
        if (s[i]<s[p]) p=i;
    for (int i=d(p);i!=p;i=d(i))
    {
        ans[k]=row(i);
        remove(i);
        for (int j=r(i);j!=i;j=r(j)) remove(j);
        if (dfs(k+1,depth)) return true;
        for (int j=l(i);j!=i;j=l(j)) resume(j);
        resume(i);
    }
    return false;
}

int main()
{
    cin>>n>>m;init();
    for (int i=1;i<=n;++i)
    {
        int x,hh=idx,tt=idx;
        for (int j=1;j<=m;++j)
        {
            scanf("%d",&x);
            if (x) add(hh,tt,i,j);
        }
    }
    int depth=0;
    while (!dfs(0,depth)) depth++;
    printf("%d\n",depth);
    for (int i=0;i<depth;++i) printf("%d ",ans[i]);
    return 0;
}

5. 例题

T1：破坏正方形

题目传送门 Luogu(RemoteJudge:UVA)

题目传送门 AcWing

可以将火柴看做行，将正方形看做列，其实就是一个重复覆盖问题了。

具体实现时，注意正方形的计算，可能会有些繁琐，需要你认真找规律。

代码略。

T2：雷达

题目传送门 AcWing

首先，我们发现，答案具有单调性，即小的可以，那么更大的半径一定可以。

二分到一个答案时，我们将雷达设为行，将城市设为列，如果一行一列为一时，代表该雷达可以覆盖该城市。

剩下就是一个重复覆盖的模板了。

注意卡常！

注意 h() 的时候不要清空，而是每一次使用一个新的编号，这样就可以避免清空。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <bitset>
using namespace std;

const int N = 1e4 + 10;
struct DLX{
    int u, d, l, r, row, col;
    #define u(x) a[x].u
    #define d(x) a[x].d
    #define l(x) a[x].l
    #define r(x) a[x].r
    #define col(x) a[x].col
    #define row(x) a[x].row
}a[N];
struct Item{
    int x, y;
}p[N];
int idx, s[1005];
int n, m, k;
int st[1005], stcnt;

void init()
{
    idx = n + 1;
    for (int i = 0; i <= n; ++ i)
        l(i) = i - 1, r(i) = i + 1, s[i] = 0, u(i) = d(i) = col(i) = i;
    r(n) = 0, l(0) = n;
}

void add(int &hh, int &tt, int x, int y)
{
    a[idx] = {y, d(y), hh, tt, x, y};
    r(hh) = l(tt) = u(d(y)) = idx;
    d(y) = idx, s[y] ++, tt = idx ++;
}

void remove(int p)
{
    for (int i = d(p); i != p; i = d(i))
        l(r(i)) = l(i), r(l(i)) = r(i);
}

void resume(int p)
{
    for (int i = u(p); i != p; i = u(i))
        l(r(i)) = r(l(i)) = i;
}

int h()
{
    int res = 0;
    ++ stcnt;
    for (int p = r(0); p; p = r(p))
    {
        if (st[col(p)] == stcnt) continue;
        st[col(p)] = stcnt, res ++;
        for (int i = d(p); i != p; i = d(i))
            for (int j = r(i); j != i; j = r(j)) st[col(j)] = stcnt;
    }
    return res;
}

int dfs(int k, int lim)
{
    if (k + h() > lim) return false;
    if (!r(0)) return true;
    int p = r(0);
    for (int i = r(0); i; i = r(i))
        if (s[i] < s[p]) p = i;
    for (int i = d(p); i != p; i = d(i))
    {
        remove(i);
        for (int j = r(i); j != i; j = r(j)) remove(j);
        if (dfs(k + 1, lim)) return true;
        for (int j = l(i); j != i; j = l(j)) resume(j);
        resume(i);
    }
    return false;
}

inline int dist2(const Item &a, const Item &b){return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);}

bool solve(double mid)
{
    memset(st, 0, sizeof st), stcnt = 0;
    init();
    for (int i = 1; i <= m; ++ i)
    {
        int hh = idx, tt = idx;
        for (int j = 1; j <= n; ++ j)
            if (1.0 * dist2(p[i], p[j + m]) <= mid * mid) add(hh, tt, i, j);
    }
    int depth = 0;
    while (depth <= k && !dfs(0, depth)) depth ++;
    return depth <= k;
}

int main()
{
    int t;cin >> t;
    while (t --)
    {
        cin >> n >> m >> k;
        for (int i = 1; i <= n; ++ i) scanf("%d %d", &p[i + m].x, &p[i + m].y);
        for (int i = 1; i <= m; ++ i) scanf("%d %d", &p[i].x, &p[i].y);
        double l = 0, r = 1500;
        while (l < r - 1e-9)
        {
            double mid = (l + r) / 2;
            if (solve(mid)) r = mid;
            else l = mid;
        }
        printf("%.6lf\n", l);
    }
    return 0;
}