【Dancing Link专题】解题报告

　　DLX用于优化精确覆盖问题，由于普通的DFS暴力搜索会超时，DLX是一个很强有力的优化手段，其实DLX的原理很简单，就是利用十字链表的快速删除和恢复特点，在DFS时删除一些行和列以减小查找规模，使得搜索深度越深而越小，然后回溯继续查找。具体资料可【点击这里】。

　　精确覆盖问题（补充）：具体一点儿就是给你一个0-1矩阵，要你找出一些行，使得每一列都有且只有一个1。

HUST 1017 Exact cover

　　入门必做，测试模板。

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 const int N = 1005;
  5 const int M = 1000005;
  6 const int head = 0;
  7 const int oo = 0x3fffffff;
  8 
  9 int U[M], D[M], L[M], R[M];
 10 int S[N], O[M], H[M];
 11 int X[M], Y[M]; // arr X record the row id and Y the column
 12 int n, m, num, sz, len;
 13 
 14 void init(int n, int m)
 15 {
 16     for(int i = 0; i <= m; i++)
 17     {
 18         U[i] = D[i] = i;
 19         L[i+1] = i;
 20         R[i] = i+1;
 21         S[i] = 0;
 22     }
 23     R[m] = 0;
 24     L[0] = m;
 25     sz = m+1;
 26 }
 27 
 28 void ins(int r, int c)
 29 {
 30     S[c]++;
 31     // 纵向插入
 32     D[U[c]] = sz;
 33     U[sz] = U[c];
 34     D[sz] = c;
 35     U[c] = sz;
 36     X[sz] = c;
 37     Y[sz] = r;
 38     // 横向插入
 39     if(H[r] == -1)
 40         H[r] = L[sz] = R[sz] = sz;
 41     else
 42     {
 43         R[L[H[r]]] = sz;
 44         L[sz] = L[H[r]];
 45         R[sz] = H[r];
 46         L[H[r]] = sz;
 47     }
 48     sz++;
 49 }
 50 
 51 void remove(const int &c)
 52 {
 53     // remove column c and all row i that A[i][c] == 1
 54     L[R[c]] = L[c];
 55     R[L[c]] = R[c];
 56     // remove column c
 57     for(int i = D[c]; i != c; i = D[i])
 58     {
 59         // remove i that A[i][c] == 1
 60         for(int j = R[i]; j != i; j = R[j])
 61         {
 62             U[D[j]] = U[j];
 63             D[U[j]] = D[j];
 64             --S[X[j]]; // decrease the count of column C[j];
 65         }
 66     }
 67 }
 68 
 69 void resume(const int &c)
 70 {
 71     // 恢复行
 72     for(int i = D[c]; i != c; i = D[i])
 73     {
 74         for(int j = R[i]; j != i; j = R[j])
 75         {
 76             ++S[X[j]];
 77             U[D[j]] = j;
 78             D[U[j]] = j;
 79         }
 80     }
 81     // 恢复一整列
 82     L[R[c]] = c;
 83     R[L[c]] = c;
 84 }
 85 
 86 bool dfs(const int &k)
 87 {
 88     if(R[head] == head)
 89     {
 90         len = k;
 91         return true;
 92     }
 93     int s(oo), c;
 94     for(int t = R[head]; t != head; t = R[t])
 95     {
 96         // select the column c which has the fewest number of element
 97         if(S[t] < s)
 98         {
 99             s = S[t];
100             c = t;
101         }
102     }
103     remove(c);
104     for(int i = D[c]; i != c; i = D[i])
105     {
106         O[k] = Y[i]; // record the answer
107         for(int j = R[i]; j != i; j = R[j])
108             remove(X[j]);
109         if(dfs(k+1)) 
110             return true;
111         for(int j = R[i]; j != i; j = R[j])
112             resume(X[j]);
113     }
114     resume(c);
115     return false;
116 }
117 
118 int main()
119 {
120     int c;
121     while(scanf("%d%d", &n, &m) != EOF)
122     {
123         init(n, m);
124         for(int i = 1; i <= n; i++)
125         {
126             scanf("%d", &num);
127             H[i] = -1;
128             for(int j = 1; j <= num; j++)
129             {
130                 scanf("%d", &c);
131                 ins(i, c);
132             }
133         }
134         if(dfs(0))
135         {
136             printf("%d", len);
137             for(int i = 0; i < len; i++)
138                 printf(" %d", O[i]);
139             putchar('
');
140         }
141         else
142             puts("NO");
143     }
144     return 0;
145 }

View Code

POJ 3740 Easy Finding

　　和上一题差不多，甚至还更简单。

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 const int N = 5005;
  5 const int M = 5005;
  6 const int head = 0;
  7 const int oo = 0x3fffffff;
  8 
  9 int U[M], D[M], L[M], R[M];
 10 int S[N], O[M], H[M];
 11 int X[M], Y[M]; 
 12 int n, m, num, sz, len;
 13 
 14 void init(int n, int m)
 15 {
 16     for(int i = 0; i <= m; i++)
 17     {
 18         U[i] = D[i] = i;
 19         L[i+1] = i;
 20         R[i] = i+1;
 21         S[i] = 0;
 22     }
 23     R[m] = 0;
 24     L[0] = m;
 25     sz = m+1;
 26 }
 27 
 28 void ins(int r, int c)
 29 {
 30     S[c]++;
 31 
 32     D[U[c]] = sz;
 33     U[sz] = U[c];
 34     D[sz] = c;
 35     U[c] = sz;
 36     X[sz] = c;
 37     Y[sz] = r;
 38 
 39     if(H[r] == -1)
 40         H[r] = L[sz] = R[sz] = sz;
 41     else
 42     {
 43         R[L[H[r]]] = sz;
 44         L[sz] = L[H[r]];
 45         R[sz] = H[r];
 46         L[H[r]] = sz;
 47     }
 48     sz++;
 49 }
 50 
 51 void remove(const int &c)
 52 {
 53     L[R[c]] = L[c];
 54     R[L[c]] = R[c];
 55     for(int i = D[c]; i != c; i = D[i])
 56     {
 57         for(int j = R[i]; j != i; j = R[j])
 58         {
 59             U[D[j]] = U[j];
 60             D[U[j]] = D[j];
 61             --S[X[j]];column C[j];
 62         }
 63     }
 64 }
 65 
 66 void resume(const int &c)
 67 {
 68     for(int i = D[c]; i != c; i = D[i])
 69     {
 70         for(int j = R[i]; j != i; j = R[j])
 71         {
 72             ++S[X[j]];
 73             U[D[j]] = j;
 74             D[U[j]] = j;
 75         }
 76     }
 77     L[R[c]] = c;
 78     R[L[c]] = c;
 79 }
 80 
 81 bool dfs(const int &k)
 82 {
 83     if(R[head] == head)
 84     {
 85         len = k;
 86         return true;
 87     }
 88     int s(oo), c;
 89     for(int t = R[head]; t != head; t = R[t])
 90     {
 91         if(S[t] < s)
 92         {
 93             s = S[t];
 94             c = t;
 95         }
 96     }
 97     remove(c);
 98     for(int i = D[c]; i != c; i = D[i])
 99     {
100         O[k] = Y[i]; // record the answer
101         for(int j = R[i]; j != i; j = R[j])
102             remove(X[j]);
103         if(dfs(k+1)) 
104             return true;
105         for(int j = R[i]; j != i; j = R[j])
106             resume(X[j]);
107     }
108     resume(c);
109     return false;
110 }
111 
112 int main()
113 {
114     int c;
115     while(scanf("%d%d", &n, &m) != EOF)
116     {
117         init(n, m);
118         for(int i = 1; i <= n; i++)
119         {
120             H[i] = -1;
121             for(int j = 1; j <= m; j++)
122             {
123                 scanf("%d", &c);
124                 if(c == 1)
125                     ins(i, j);
126             }
127         }
128         if(dfs(0))
129             puts("Yes, I found it");
130         else
131             puts("It is impossible");
132     }
133     return 0;
134 }

View Code

ZOJ 3209 Treasure Map

　　将二维变一维，离散化，每个点坐标对应一列，DLX一共有p行n*m列，直接构造即可。（ZOJ里面没有RE吗？我数组开小了返回TLE，很郁闷）。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 const int N = 55;
  5 const int M = 1001001;
  6 const int head = 0;
  7 const int oo = 0x3f3f3f3f;
  8 
  9 int U[M], D[M], L[M], R[M];
 10 int S[N], O[M], H[M];
 11 int X[M], Y[M];
 12 int n, m, num, sz, len, p;
 13 int ans;
 14 
 15 void init(int n, int m)
 16 {
 17     for(int i = 0; i <= m; i++)
 18     {
 19         U[i] = D[i] = i;
 20         L[i+1] = i;
 21         R[i] = i+1;
 22         S[i] = 0;
 23     }
 24     R[m] = 0;
 25     L[0] = m;
 26     sz = m+1;
 27 }
 28 
 29 void ins(int r, int c)
 30 {
 31     S[c]++;
 32     D[U[c]] = sz;
 33     U[sz] = U[c];
 34     D[sz] = c;
 35     U[c] = sz;
 36     X[sz] = c;
 37     Y[sz] = r;
 38     if(H[r] == -1)
 39         H[r] = L[sz] = R[sz] = sz;
 40     else
 41     {
 42         R[L[H[r]]] = sz;
 43         L[sz] = L[H[r]];
 44         R[sz] = H[r];
 45         L[H[r]] = sz;
 46     }
 47     sz++;
 48 }
 49 
 50 void remove(const int &c)
 51 {
 52     L[R[c]] = L[c];
 53     R[L[c]] = R[c];
 54     for(int i = D[c]; i != c; i = D[i])
 55     {
 56         for(int j = R[i]; j != i; j = R[j])
 57         {
 58             U[D[j]] = U[j];
 59             D[U[j]] = D[j];
 60             --S[X[j]];
 61         }
 62     }
 63 }
 64 
 65 void resume(const int &c)
 66 {
 67     for(int i = D[c]; i != c; i = D[i])
 68     {
 69         for(int j = R[i]; j != i; j = R[j])
 70         {
 71             ++S[X[j]];
 72             U[D[j]] = j;
 73             D[U[j]] = j;
 74         }
 75     }
 76     L[R[c]] = c;
 77     R[L[c]] = c;
 78 }
 79 
 80 void dfs(const int &k)
 81 {
 82     if(k >= ans) return ;
 83     if(R[head] == head)
 84     {
 85         ans = std::min(ans, k);
 86         return;
 87     }
 88     int s(oo), c;
 89     for(int t = R[head]; t != head; t = R[t])
 90     {
 91         if(S[t] < s)
 92         {
 93             s = S[t];
 94             c = t;
 95         }
 96     }
 97     remove(c);
 98     for(int i = D[c]; i != c; i = D[i])
 99     {
100         O[k] = Y[i]; 
101         for(int j = R[i]; j != i; j = R[j])
102             remove(X[j]);
103         dfs(k+1);
104         for(int j = L[i]; j != i; j = L[j])
105             resume(X[j]);
106     }
107     resume(c);
108 }
109 
110 int main()
111 {
112     int x1, y1, x2, y2;
113     int cas;
114     scanf("%d", &cas);
115     while(cas--)
116     {
117         scanf("%d%d%d", &n, &m, &p);
118         init(n, n*m);
119         for(int i = 1; i <= p; i++)
120         {
121             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
122             H[i] = -1;
123             for(int j = x1; j < x2; j++)
124                 for(int k = y1; k < y2; k++)
125                     ins(i, j*m+k+1);
126         }
127         ans = oo;
128         dfs(0);
129         printf("%d
", ans == oo ? -1 : ans);
130     }
131     return 0;
132 }

View Code

POJ 3074 Sudoku

　　用Dancing Link是解决数独问题的利器。具体也可以参考博文开头给出的资料链接。

　　看完那篇文章后，我就在想：Dancing Link解数独问题中，为什么要另外用81列来限制数独是否已经填满？：在行列宫的唯一性被完全覆盖的情况下（81*3列）已经说明数独已经填满了吗？想了好久才想明白，其实这个问题非常简单，如果不用81列来限制，数独每个位置只填一个数，那么会出现即使行列宫唯一性都满足的前提下有些格子被两个数覆盖，从反面想，如果没有了81列来限制数独是否填满，那么我们构造出的列为:

　　行1填1 行1填2 行1填3 ... 列1填1 列1填2 列1填3 ... 宫1有1 宫1有2 宫1有3 ...

　　那么，可以有(1,1,1)和(1,1,2)同时合法并覆盖“行1填1,行1填2,列1填1,列1填2”，但显然，这是不合法的，因为一个格子只能填一个数！终于想通了啊。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 const int A = 9;
  5 const int N = A*A*A+5;
  6 const int M = (A+A+A)*A+A*A+5;
  7 const int head = 0;
  8 const int oo = 0x3f3f3f3f;
  9 
 10 
 11 int U[N*M], D[N*M], L[N*M], R[N*M];
 12 int S[N*M], O[N*M], H[N*M];
 13 int X[N*M], Y[N*M];
 14 int n, num, sz, len, p;
 15 bool g[N][M];
 16 char s[100];
 17 int ans[N][M];
 18 
 19 void init(int m)
 20 {
 21     for(int i = 0; i <= m; i++)
 22     {
 23         U[i] = D[i] = i;
 24         L[i+1] = i;
 25         R[i] = i+1;
 26         S[i] = 0;
 27     }
 28     R[m] = 0;
 29     L[0] = m;
 30     sz = m+1;
 31 }
 32 
 33 void ins(int r, int c)
 34 {
 35     S[c]++;
 36     D[U[c]] = sz;
 37     U[sz] = U[c];
 38     D[sz] = c;
 39     U[c] = sz;
 40     X[sz] = c;
 41     Y[sz] = r;
 42     if(H[r] == -1)
 43         H[r] = L[sz] = R[sz] = sz;
 44     else
 45     {
 46         R[L[H[r]]] = sz;
 47         L[sz] = L[H[r]];
 48         R[sz] = H[r];
 49         L[H[r]] = sz;
 50     }
 51     sz++;
 52 }
 53 
 54 void remove(const int &c)
 55 {
 56     L[R[c]] = L[c];
 57     R[L[c]] = R[c];
 58     for(int i = D[c]; i != c; i = D[i])
 59     {
 60         for(int j = R[i]; j != i; j = R[j])
 61         {
 62             U[D[j]] = U[j];
 63             D[U[j]] = D[j];
 64             --S[X[j]];
 65         }
 66     }
 67 }
 68 
 69 void resume(const int &c)
 70 {
 71     for(int i = D[c]; i != c; i = D[i])
 72     {
 73         for(int j = R[i]; j != i; j = R[j])
 74         {
 75             ++S[X[j]];
 76             U[D[j]] = j;
 77             D[U[j]] = j;
 78         }
 79     }
 80     L[R[c]] = c;
 81     R[L[c]] = c;
 82 }
 83 
 84 bool dfs(const int &k)
 85 {
 86     if(R[head] == head)
 87         return true;
 88         
 89     int s(oo), c;
 90     for(int t = R[head]; t != head; t = R[t])
 91     {
 92         if(S[t] < s)
 93         {
 94             s = S[t];
 95             c = t;
 96         }
 97     }
 98     remove(c);
 99     for(int i = D[c]; i != c; i = D[i])
100     {
101         ans[Y[i]/81][Y[i]%81/9] = Y[i]%9+1;
102         for(int j = R[i]; j != i; j = R[j])
103             remove(X[j]);
104         if(dfs(k+1))
105             return true;
106         for(int j = L[i]; j != i; j = L[j])
107             resume(X[j]);
108     }
109     resume(c);
110     return false;
111 }
112 
113 void love(int i, int j, int k)
114 {
115     int row = (i*9+j)*9+k;
116     g[row][i*9+j] = true;
117     g[row][81*1+i*9+k] = true;
118     g[row][81*2+j*9+k] = true;
119     int a = i/3, b = j/3;
120     g[row][81*3 + (a*3+b)*9+k] = true;
121 }
122 
123 int main()
124 {
125     while(scanf("%s", s) != EOF)
126     {
127         if(strcmp(s, "end") ==0 ) break;
128         init(A*A*4);
129         memset(g, false, sizeof g);
130         memset(H, -1, sizeof H);
131         for(int i = 0; i < A; i++)
132         {
133             for(int j = 0; j < A; j++)
134             {
135                 if(s[i*A+j] != '.')
136                 {
137                     int k = s[i*A+j]-'1';
138                     love(i, j, k);
139                 }
140                 else
141                 {
142                     for(int k = 0; k < A; k++)
143                         love(i, j, k);
144                 }
145             }
146         }
147         for(int i = 0; i < N; i++)
148             for(int j = 0; j < M; j++)
149                 if(g[i][j])
150                     ins(i, j+1); // column id begin from 1, not 0, so j plus 1
151         
152         dfs(0);
153         for(int i = 0; i < 9; i++)
154             for(int j = 0; j < 9; j++)
155                 printf("%d", ans[i][j]);
156         putchar('
');
157     }
158     return 0;
159 }

View Code

POJ 3076 Sudoku

　　和POJ3074一样,只不过是16*16的数独。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 const int A = 16;
  5 const int N = A*A*A+5;
  6 const int M = A*A*4+5;
  7 const int head = 0;
  8 const int oo = 0x3f3f3f3f;
  9 
 10 int U[N*M], D[N*M], L[N*M], R[N*M];
 11 int S[N*M], O[N*M], H[N*M];
 12 int X[N*M], Y[N*M];
 13 int n, num, sz, len, p;
 14 bool g[N][M];
 15 char s[20][20];
 16 int ans[N][M];
 17 
 18 void init(int m)
 19 {
 20     for(int i = 0; i <= m; i++)
 21     {
 22         U[i] = D[i] = i;
 23         L[i+1] = i;
 24         R[i] = i+1;
 25         S[i] = 0;
 26     }
 27     R[m] = 0;
 28     L[0] = m;
 29     sz = m+1;
 30 }
 31 
 32 void ins(int r, int c)
 33 {
 34     S[c]++;
 35     D[U[c]] = sz;
 36     U[sz] = U[c];
 37     D[sz] = c;
 38     U[c] = sz;
 39     X[sz] = c;
 40     Y[sz] = r;
 41     if(H[r] == -1)
 42         H[r] = L[sz] = R[sz] = sz;
 43     else
 44     {
 45         R[L[H[r]]] = sz;
 46         L[sz] = L[H[r]];
 47         R[sz] = H[r];
 48         L[H[r]] = sz;
 49     }
 50     sz++;
 51 }
 52 
 53 void remove(const int &c)
 54 {
 55     L[R[c]] = L[c];
 56     R[L[c]] = R[c];
 57     for(int i = D[c]; i != c; i = D[i])
 58     {
 59         for(int j = R[i]; j != i; j = R[j])
 60         {
 61             U[D[j]] = U[j];
 62             D[U[j]] = D[j];
 63             --S[X[j]];
 64         }
 65     }
 66 }
 67 
 68 void resume(const int &c)
 69 {
 70     for(int i = D[c]; i != c; i = D[i])
 71     {
 72         for(int j = R[i]; j != i; j = R[j])
 73         {
 74             ++S[X[j]];
 75             U[D[j]] = j;
 76             D[U[j]] = j;
 77         }
 78     }
 79     L[R[c]] = c;
 80     R[L[c]] = c;
 81 }
 82 
 83 bool dfs(const int &k)
 84 {
 85     if(R[head] == head)
 86         return true;
 87         
 88     int s(oo), c;
 89     for(int t = R[head]; t != head; t = R[t])
 90     {
 91         if(S[t] < s)
 92         {
 93             s = S[t];
 94             c = t;
 95         }
 96     }
 97     remove(c);
 98     for(int i = D[c]; i != c; i = D[i])
 99     {
100         ans[Y[i]/(A*A)][Y[i]%(A*A)/A] = Y[i]%A;
101         for(int j = R[i]; j != i; j = R[j])
102             remove(X[j]);
103         if(dfs(k+1))
104             return true;
105         for(int j = L[i]; j != i; j = L[j])
106             resume(X[j]);
107     }
108     resume(c);
109     return false;
110 }
111 
112 void love(int i, int j, int k)
113 {
114     int row = (i*A+j)*A+k;
115     g[row][i*A+j] = true;
116     g[row][A*A*1+i*A+k] = true;
117     g[row][A*A*2+j*A+k] = true;
118     int a = i/4, b = j/4;
119     g[row][A*A*3 + (a*4+b)*A+k] = true;
120 }
121 
122 int main()
123 {
124     bool flag = false;
125     while(scanf("%s", s[0]) != EOF)
126     {
127         for(int i = 1; i < A; i++)
128             scanf("%s", s[i]);
129         if(flag) putchar('
');
130         flag = true;
131         init(A*A*4);
132         memset(g, false, sizeof g);
133         memset(H, -1, sizeof H);
134         for(int i = 0; i < A; i++)
135         {
136             for(int j = 0; j < A; j++)
137             {
138                 if(s[i][j] != '-')
139                 {
140                     int k = s[i][j] -'A';
141                     love(i, j, k);
142                 }
143                 else
144                 {
145                     for(int k = 0; k < A; k++)
146                         love(i, j, k);
147                 }
148             }
149         }
150         for(int i = 0; i < N; i++)
151             for(int j = 0; j < M; j++)
152                 if(g[i][j])
153                     ins(i, j+1);
154         
155         dfs(0);
156         for(int i = 0; i < A; i++)
157         {
158             for(int j = 0; j < A; j++)
159                 putchar(ans[i][j]+'A');
160             putchar('
');
161         }
162     }
163     return 0;
164 }

View Code

POJ2676 HDU2780 HDU3111 都是差不多的，不提。

HDU 3909 Sudoku

　　这道题总的来说是简单的，弄清题意就行。这道题我对DLX解数独更进一步了解了，在dfs函数中，要想得到一个解，那么必须在找到一个解的时候return true，如果不设返回值，那么得到的解会被后面的继续深搜覆盖掉，所以要及时返回。如果想知道是否有多个解，那么，可以新建变量cnt进行计数。

  1 #include <vector>
  2 #include <list>
  3 #include <map>
  4 #include <set>
  5 #include <queue>
  6 #include <deque>
  7 #include <stack>
  8 #include <algorithm>
  9 #include <sstream>
 10 #include <iostream>
 11 #include <iomanip>
 12 #include <cstdio>
 13 #include <cstdlib>
 14 #include <cstring>
 15 #include <queue>
 16 #include <cmath>
 17 using namespace std;
 18 #define pii         pair<int,int>
 19 #define clr(a)      memset((a),0,sizeof (a))
 20 #define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
 21 #define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
 22 #define oo          0x3f3f3f3f
 23 #define eps         1e-6
 24 #define N           (16*16*16+5)
 25 #define M           (16*16*4+5)
 26 #define mod         1000000007
 27 #define MP          make_pair
 28 #define PB          push_back
 29 #define RI(x)       scanf("%d",&x)
 30 #define RII(x,y)    scanf("%d%d",&x,&y)
 31 #define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
 32 typedef long long LL;
 33 
 34 const int head = 0;
 35 
 36 int A;
 37 int U[N*M], D[N*M], L[N*M], R[N*M];
 38 int S[N*M], O[N*M], H[N*M];
 39 int X[N*M], Y[N*M];
 40 int n, num, sz, len, p;
 41 bool g[N][M];
 42 char s[20][20];
 43 int ans[20][20], b[20][20], cnt;
 44 
 45 void init(int m)
 46 {
 47     for(int i = 0; i <= m; i++)
 48     {
 49         U[i] = D[i] = i;
 50         L[i+1] = i;
 51         R[i] = i+1;
 52         S[i] = 0;
 53     }
 54     R[m] = 0;
 55     L[0] = m;
 56     sz = m+1;
 57 }
 58 
 59 void ins(int r, int c)
 60 {
 61     S[c]++;
 62     D[U[c]] = sz;
 63     U[sz] = U[c];
 64     D[sz] = c;
 65     U[c] = sz;
 66     X[sz] = c;
 67     Y[sz] = r;
 68     if(H[r] == -1)
 69         H[r] = L[sz] = R[sz] = sz;
 70     else
 71     {
 72         R[L[H[r]]] = sz;
 73         L[sz] = L[H[r]];
 74         R[sz] = H[r];
 75         L[H[r]] = sz;
 76     }
 77     sz++;
 78 }
 79 
 80 void remove(const int &c)
 81 {
 82     L[R[c]] = L[c];
 83     R[L[c]] = R[c];
 84     for(int i = D[c]; i != c; i = D[i])
 85     {
 86         for(int j = R[i]; j != i; j = R[j])
 87         {
 88             U[D[j]] = U[j];
 89             D[U[j]] = D[j];
 90             --S[X[j]];
 91         }
 92     }
 93 }
 94 
 95 void resume(const int &c)
 96 {
 97     for(int i = D[c]; i != c; i = D[i])
 98     {
 99         for(int j = R[i]; j != i; j = R[j])
100         {
101             ++S[X[j]];
102             U[D[j]] = j;
103             D[U[j]] = j;
104         }
105     }
106     L[R[c]] = c;
107     R[L[c]] = c;
108 }
109 
110 
111 bool dfs(const int &k, bool f)
112 {
113     if(R[head] == head)
114     {
115         if(cnt || f)
116         {
117             cnt++;
118             return true;
119         }
120         cnt++;
121         return false;
122     }
123     int s(oo), c;
124     for(int t = R[head]; t != head; t = R[t])
125     {
126         if(S[t] < s)
127         {
128             s = S[t];
129             c = t;
130         }
131     }
132     remove(c);
133     for(int i = D[c]; i != c; i = D[i])
134     {
135         ans[Y[i]/(A*A)][Y[i]%(A*A)/A] = Y[i]%A+1;
136         for(int j = R[i]; j != i; j = R[j])
137             remove(X[j]);
138         if(dfs(k+1, f)) return true;
139         for(int j = L[i]; j != i; j = L[j])
140             resume(X[j]);
141     }
142     resume(c);
143     return false;
144 }
145 
146 void love(int i, int j, int k)
147 {
148     int row = (i*A+j)*A+k;
149     g[row][i*A+j] = true;
150     g[row][A*A*1+i*A+k] = true;
151     g[row][A*A*2+j*A+k] = true;
152     int p = (int)sqrt(A);
153     int a = i/p, b = j/p;
154     g[row][A*A*3 + (a*p+b)*A+k] = true;
155 }
156 
157 
158 void solve()
159 {
160     cnt = 0;
161     init(A*A*4);
162     memset(g, false, sizeof g);
163     memset(H, -1, sizeof H);
164     for(int i = 0; i < A; i++)
165     {
166         for(int j = 0; j < A; j++)
167         {
168             if(s[i][j] != '.')
169             {
170                 int k;
171                 if(s[i][j] >= '1' && s[i][j] <= '9') k = s[i][j] - '1';
172                 else k = s[i][j] - 'A' + 9;
173                 love(i, j, k);
174             }
175             else
176             {
177                 for(int k = 0; k < A; k++)
178                     love(i, j, k);
179             }
180         }
181     }
182     for(int i = 0; i < N; i++)
183     {
184         for(int j = 0; j < M; j++)
185         {
186             if(g[i][j])
187                 ins(i, j+1);
188         }
189     }
190 }
191 
192 int main()
193 {
194     while(RI(A) != EOF)
195     {
196         A = A * A;
197         rep(i,0,A-1)
198             scanf("%s", s[i]);
199         solve();
200         dfs(0, 0);
201         if(cnt == 0)
202         {
203             puts("No Solution");
204             continue;
205         }
206         else if(cnt > 1)
207         {
208             puts("Multiple Solutions");
209             continue;
210         }
211         for(int i = 0; i < A; i++)
212         {
213             for(int j = 0; j < A; j++)
214             {
215                 if(s[i][j] != '.')
216                 {
217                     char c = s[i][j];
218                     s[i][j] = '.';
219                     solve();
220                     dfs(0, 0);
221                     if(cnt < 2)
222                         goto end ;
223                     s[i][j] = c;
224                 }
225             }
226         }
227         solve();
228         dfs(0, 1);
229         for(int i = 0; i < A; i++)
230         {
231             for(int j = 0; j < A; j++)
232             {
233                 if(ans[i][j] <= 9)
234                     printf("%d", ans[i][j]);
235                 else
236                     printf("%c", ans[i][j]-10+'A');
237             }
238             putchar('
');
239         }
240         continue;
241         end:
242             puts("Not Minimal");
243     }
244     return 0;
245 }

View Code

HDU 3663 Power Stations

　　很不错的一道题。

　　首先，对于列来说，我们需要每个城市在D天里都要有电供应，那么，我们需要D*n列表示每个成绩每一天的状态。对于行，我们需要建立n*25行表示第i个城市作为发电站各个发电时间区间的值，比如，对于区间[1,3]，我们拆成[0,0],[1,1],[1,2],[1,3],[2,3],[3,3]（拆成25行为了方便计算，实际上有些样例不需要这么多行，空行不影响结果）。但是，现在有一个问题需要面对：一个发电站发电区间只能选一个。为此，新开n行，表示如果某个城市选择了一个区间，就锁定该城市。还要注意重边情况。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 const int N = 2005;
  5 const int M = 505;
  6 const int oo = 0x3f3f3f3f;
  7 
  8 int U[N*M], D[N*M], L[N*M], R[N*M];
  9 int S[N*M], O[N*M], H[N*M];
 10 int X[N*M], Y[N*M];
 11 int n, m, d, num, sz, len, p;
 12 int g[N][M];
 13 
 14 int hh[65][65];
 15 
 16 struct Node
 17 {
 18     int s, e;
 19 }ans[N];
 20 
 21 void init(int m)
 22 {
 23     for(int i = 0; i <= m; i++)
 24     {
 25         U[i] = D[i] = i;
 26         L[i+1] = i;
 27         R[i] = i+1;
 28         S[i] = 0;
 29     }
 30     R[m] = 0;
 31     L[0] = m;
 32     sz = m+1;
 33 }
 34 
 35 void ins(int r, int c)
 36 {
 37     S[c]++;
 38     D[U[c]] = sz;
 39     U[sz] = U[c];
 40     D[sz] = c;
 41     U[c] = sz;
 42     X[sz] = c;
 43     Y[sz] = r;
 44     if(H[r] == -1)
 45         H[r] = L[sz] = R[sz] = sz;
 46     else
 47     {
 48         R[L[H[r]]] = sz;
 49         L[sz] = L[H[r]];
 50         R[sz] = H[r];
 51         L[H[r]] = sz;
 52     }
 53     sz++;
 54 }
 55 
 56 void remove(const int &c)
 57 {
 58     L[R[c]] = L[c];
 59     R[L[c]] = R[c];
 60     for(int i = D[c]; i != c; i = D[i])
 61     {
 62         for(int j = R[i]; j != i; j = R[j])
 63         {
 64             U[D[j]] = U[j];
 65             D[U[j]] = D[j];
 66             --S[X[j]];
 67         }
 68     }
 69 }
 70 
 71 void resume(const int &c)
 72 {
 73     for(int i = D[c]; i != c; i = D[i])
 74     {
 75         for(int j = R[i]; j != i; j = R[j])
 76         {
 77             ++S[X[j]];
 78             U[D[j]] = j;
 79             D[U[j]] = j;
 80         }
 81     }
 82     L[R[c]] = c;
 83     R[L[c]] = c;
 84 }
 85 
 86 bool dfs(const int &k)
 87 {
 88     if(R[0] == 0)
 89     {
 90         O[k] = -1;
 91         return true;
 92     }
 93     int s(oo), c;
 94     for(int t = R[0]; t != 0; t = R[t])
 95     {
 96         if(S[t] < s)
 97         {
 98             s = S[t];
 99             c = t;
100         }
101     }
102     remove(c);
103     for(int i = D[c]; i != c; i = D[i])
104     {
105         O[k] = Y[i];
106         for(int j = R[i]; j != i; j = R[j])
107             remove(X[j]);
108         if(dfs(k+1))
109             return true;
110         for(int j = L[i]; j != i; j = L[j])
111             resume(X[j]);
112     }
113     resume(c);
114     return false;
115 }
116 
117 int main()
118 {
119     int a, b;
120     while(scanf("%d%d%d", &n, &m, &d) != EOF)
121     {
122         memset(hh, 0, sizeof hh);
123         memset(g, 0, sizeof g);
124         memset(H, -1, sizeof H);
125         for(int i = 0; i < m; i++)
126         {
127             scanf("%d%d", &a, &b);
128             hh[a][b] = hh[b][a] = 1;
129         }
130         init(d*n+n);
131         for(int i = 0; i < n; i++)
132         {
133             scanf("%d%d", &a, &b);
134             for(int j = a-1; j < b; j++)
135             {
136                 for(int k = j; k < b; k++)
137                 {
138                     for(int u = j; u <= k; u++)
139                     {
140                         g[i*25+j*5+k][u*n+i+1] = 1;
141                         g[i*25+j*5+k][d*n+i+1] = 1;
142                         for(int v = 1; v <= n; v++)
143                             if(hh[i+1][v])
144                                 g[i*25+j*5+k][u*n+v] = 1;
145                     }
146                 }
147             }
148         }
149         for(int i = 0; i < n; i++) // 每个城市的[0,0]区间
150             g[25*n+i][d*n+i+1] = 1;
151         for(int i = 0; i < n*25+n; i++)
152             for(int j = 1; j <= d*n+n; j++)
153                 if(g[i][j]) ins(i, j);
154 
155         if(!dfs(0))
156             puts("No solution
");
157         else
158         {
159             memset(ans, 0, sizeof ans);
160             for(int i = 0; O[i] != -1; i++)
161             {
162                 if(O[i] >= 25*n) continue;
163                 ans[O[i]/25+1].s = O[i]%25/5+1;
164                 ans[O[i]/25+1].e = O[i]%5+1;
165             }
166             for(int i = 1; i <= n; i++)
167                 printf("%d %d
", ans[i].s, ans[i].e);
168             putchar('
');
169         }
170     }
171     return 0;
172 }

View Code