第35届ACM/ICPC亚洲区预选赛哈尔滨赛区的 1004 题，Power Stations。
Dancing Links，相对于其他的 DLX 来说，这道题目应该还算简单的。
1 /*
2 * File: Herbin 1004 Power Stations
3 * Author: xiaotian @ hnu
4 * Created on 2010年9月29日, 下午12:24
5 * 题解：经典的 Dancing Links 精确覆盖题目。题目挂在杭电。
6 * 以每一个 town 的每一天分别为行和列去建图。见图应该是比较容易想到的，也比较裸。
7 * 某一个 town 在他工作的那个时间段可以覆盖他自己和及与他相邻的的 town 。以此为依据建图。
8 * 这道题麻烦在每一个 town 的 power station 只能用一次。
9 * 也就是说你不能先用一段时间关掉，再过一段时间后又打开。这样是不合法的。
10 * 那么就必须在搜索的过程中实时判断解的合法性。只要有一组解合法就可以了。具体见 dfs 函数。
11 */
12 #include<iostream>
13 #include<cstdio>
14 #include<string.h>
15 #include<vector>
16 #include<math.h>
17 #define inf 0x3fffffff
18 using namespace std;
19 const int N = 305;
20 const int M = 4000;
21 int map[N][N];
22 vector<int>g[65];
23 int out[N];
24 int beg[65], end[65];
25 int U[M], D[M], R[M], L[M], rs[N];
26 int size[N], head, row[M], col[M];
27 int n, m, k;
28 int nodecnt, maxdepth;
29 struct point
30 {
31 int x,y;
32 point(int xx=0,int yy=0):x(xx),y(yy){}
33 };
34 point shu[65];
35 void read() {
36 int i, j;
37 for (i = 0; i <= n; i++) {
38 g[i].clear();
39 g[i].push_back(i);
40 }
41 for (i = 0; i < m; i++) {
42 int a, b;
43 scanf("%d%d", &a, &b);
44 a--, b--;
45 g[a].push_back(b);
46 g[b].push_back(a);
47 }
48 for (i = 0; i < n; i++) scanf("%d%d", beg + i, end + i);
49 }
50
51 void init(int m) {
52 memset(size, 0, sizeof (size));
53 memset(col, -1, sizeof (col));
54 nodecnt = m + 1;
55 for (int i = 0; i <= m; i++) {
56 L[i] = (i - 1);
57 R[i] = (i + 1);
58 col[i] = i;
59 D[i] = U[i] = i;
60 }
61 L[0] = m;
62 R[m] = 0;
63 size[0] = INT_MAX;
64 }
65 int ans[N];
66 int len;
67 bool yes;
68
69 inline void remove(int id) {
70 int i, j;
71 R[ L[id] ] = R[id];
72 L[ R[id] ] = L[id];
73 for (i = D[id]; i != id; i = D[i])
74 for (j = R[i]; j != i; j = R[j]) {
75 U[ D[j] ] = U[j];
76 D[ U[j] ] = D[j];
77 size[ col[j] ]--;
78 }
79 }
80
81 inline void resume(int id) {
82 int i, j;
83 for (i = U[id]; i != id; i = U[i])
84 for (j = L[i]; j != i; j = L[j]) {
85 size[ col[j] ]++;
86 U[ D[j] ] = j;
87 D[ U[j] ] = j;
88 }
89 R[ L[id] ] = id;
90 L[ R[id] ] = id;
91 }
92
93 int ansL;
94
95 int output() {
96 memset(out, 0, sizeof (out));
97 for (int i = 0; i < ansL; i++) {
98 out[ans[i]] = 1;
99 }
100 for (int i = 0; i < n; i++) {
101 int a, b;
102 a = b = 0;
103 for (int j = 1; j <= k; j++) {
104 if (j == 1) {
105 if (out[i * k + j] == 1) a = j;
106 } else {
107 if (out[i * k + j] == 1 && out[i * k + j - 1] == 0)
108 {
109 if(a) return 0;
110 else a = j;
111 }
112 }
113 if (j == k) {
114 if (out[i * k + j] == 1) b = j;
115 } else {
116 if (out[i * k + j] == 1 && out[i * k + j + 1] == 0)
117 {
118 if(b) return 0;
119 else b = j;
120 }
121 }
122 }
123 shu[i]=point(a,b);
124 }
125 return 1;
126 }
127
128 void dfs1(int num) {
129 if (R[0] == 0) {
130 ansL = num;
131 yes = output();
132 if(yes)
133 {
134 for(int i=0;i<n;i++) printf("%d %d\n",shu[i].x,shu[i].y);
135 puts("");
136 }
137 return;
138 }
139 int i, j, id = 0, min = inf;
140 for (i = R[0]; i != 0; i = R[i])
141 if (size[i] < min) {
142 min = size[i];
143 id = i;
144 }
145 remove(id);
146 for (i = D[id]; i != id; i = D[i]) {
147 ans[num] = row[i];
148 for (j = R[i]; j != i; j = R[j])
149 remove(col[j]);
150 dfs1(num + 1);
151 if (yes) return;
152 for (j = L[i]; j != i; j = L[j])
153 resume(col[j]);
154 }
155 resume(id);
156 }
157
158 inline void insert(int i, int *tt, int c) {
159 for (int j = 0; j < c; j++, nodecnt++) {
160 int x = tt[j];
161 row[nodecnt] = i;
162 col[nodecnt] = x;
163 size[x]++;
164 U[nodecnt] = x;
165 D[nodecnt] = D[x];
166 U[D[x]] = nodecnt;
167 D[x] = nodecnt;
168 if (j == 0) L[nodecnt] = R[nodecnt] = nodecnt;
169 else {
170 L[nodecnt] = nodecnt - 1;
171 R[nodecnt] = nodecnt - j;
172 R[nodecnt - 1] = nodecnt;
173 L[nodecnt - j] = nodecnt;
174 }
175 }
176 }
177
178 void build() {
179 init(n * k);
180 int tt[305], c = 0;
181 int t = n * k + 1;
182 for (int i = 1; i < t; i++) {
183 c = 0;
184 for (int j = 1; j < t; j++)
185 if (map[i][j] == 1) tt[c++] = j;
186 insert(i, tt, c);
187 }
188 }
189
190 void solve() {
191 memset(map, 0, sizeof (map));
192 for (int i = 0; i < n; i++) {
193 for (int j = beg[i]; j <= end[i]; j++) {
194 for (int a = 0; a < g[i].size(); a++) {
195 map[i * k + j][g[i][a] * k + j] = 1;
196 }
197 }
198 }
199 memset(out, 0, sizeof (out));
200 int flag = 0;
201 while (flag < 1) {
202 build();
203 ansL = inf;
204 yes = false;
205 dfs1(0);
206 if (yes == false) {
207 puts("No solution\n");
208 return;
209 }
210 flag++;
211 }
212 }
213
214 int main() {
215 //freopen("in.txt", "r", stdin);
216 //freopen("out.txt", "w", stdout);
217 while (scanf("%d%d%d", &n, &m, &k) != EOF) {
218 read();
219 solve();
220 }
221 return 0;
222 }
添加几组测试数据：
3 3 5
1 2
2 3
3 1
1 5
1 5
1 5
4 4 5
1 2
2 3
3 4
4 1
1 5
1 5
1 5
1 5
2 1 5
1 2
1 2
3 5
6 5 5
1 2
1 3
1 4
1 5
1 6
1 5
3 5
2 3
1 3
2 3
3 4
6 9 5
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
1 5
3 4
1 2
2 3
1 3
3 5
输出: (spj题目,输出不唯一).
0 0
0 0
1 5
No solution
1 2
3 5
1 5
0 0
0 0
0 0
0 0
0 0
1 5
0 0
0 0
0 0
0 0
0 0