【Dancing Link专题】解题报告
2024-10-19 04:32:54
DLX用于优化精确覆盖问题，由于普通的DFS暴力搜索会超时，DLX是一个很强有力的优化手段，其实DLX的原理很简单，就是利用十字链表的快速删除和恢复特点，在DFS时删除一些行和列以减小查找规模，使得搜索深度越深而越小，然后回溯继续查找。具体资料可【点击这里】。
精确覆盖问题（补充）：具体一点儿就是给你一个0-1矩阵，要你找出一些行，使得每一列都有且只有一个1。
HUST 1017 Exact cover
入门必做，测试模板。
#include <stdio.h>
#include <string.h> const int N = ;
const int M = ;
const int head = ;
const int oo = 0x3fffffff; int U[M], D[M], L[M], R[M];
int S[N], O[M], H[M];
int X[M], Y[M]; // arr X record the row id and Y the column
int n, m, num, sz, len; void init(int n, int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++;
// 纵向插入
D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r;
// 横向插入
if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
// remove column c and all row i that A[i][c] == 1
L[R[c]] = L[c];
R[L[c]] = R[c];
// remove column c
for(int i = D[c]; i != c; i = D[i])
{
// remove i that A[i][c] == 1
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]]; // decrease the count of column C[j];
}
}
} void resume(const int &c)
{
// 恢复行
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
// 恢复一整列
L[R[c]] = c;
R[L[c]] = c;
} bool dfs(const int &k)
{
if(R[head] == head)
{
len = k;
return true;
}
int s(oo), c;
for(int t = R[head]; t != head; t = R[t])
{
// select the column c which has the fewest number of element
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
O[k] = Y[i]; // record the answer
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
if(dfs(k+))
return true;
for(int j = R[i]; j != i; j = R[j])
resume(X[j]);
}
resume(c);
return false;
} int main()
{
int c;
while(scanf("%d%d", &n, &m) != EOF)
{
init(n, m);
for(int i = ; i <= n; i++)
{
scanf("%d", &num);
H[i] = -;
for(int j = ; j <= num; j++)
{
scanf("%d", &c);
ins(i, c);
}
}
if(dfs())
{
printf("%d", len);
for(int i = ; i < len; i++)
printf(" %d", O[i]);
putchar('\n');
}
else
puts("NO");
}
return ;
}
POJ 3740 Easy Finding
和上一题差不多，甚至还更简单。
#include <stdio.h>
#include <string.h> const int N = ;
const int M = ;
const int head = ;
const int oo = 0x3fffffff; int U[M], D[M], L[M], R[M];
int S[N], O[M], H[M];
int X[M], Y[M];
int n, m, num, sz, len; void init(int n, int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++; D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r; if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]];column C[j];
}
}
} void resume(const int &c)
{
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
} bool dfs(const int &k)
{
if(R[head] == head)
{
len = k;
return true;
}
int s(oo), c;
for(int t = R[head]; t != head; t = R[t])
{
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
O[k] = Y[i]; // record the answer
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
if(dfs(k+))
return true;
for(int j = R[i]; j != i; j = R[j])
resume(X[j]);
}
resume(c);
return false;
} int main()
{
int c;
while(scanf("%d%d", &n, &m) != EOF)
{
init(n, m);
for(int i = ; i <= n; i++)
{
H[i] = -;
for(int j = ; j <= m; j++)
{
scanf("%d", &c);
if(c == )
ins(i, j);
}
}
if(dfs())
puts("Yes, I found it");
else
puts("It is impossible");
}
return ;
}
ZOJ 3209 Treasure Map
将二维变一维，离散化，每个点坐标对应一列，DLX一共有p行n*m列，直接构造即可。（ZOJ里面没有RE吗？我数组开小了返回TLE，很郁闷）。
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = ;
const int M = ;
const int head = ;
const int oo = 0x3f3f3f3f; int U[M], D[M], L[M], R[M];
int S[N], O[M], H[M];
int X[M], Y[M];
int n, m, num, sz, len, p;
int ans; void init(int n, int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++;
D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r;
if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]];
}
}
} void resume(const int &c)
{
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
} void dfs(const int &k)
{
if(k >= ans) return ;
if(R[head] == head)
{
ans = std::min(ans, k);
return;
}
int s(oo), c;
for(int t = R[head]; t != head; t = R[t])
{
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
O[k] = Y[i];
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
dfs(k+);
for(int j = L[i]; j != i; j = L[j])
resume(X[j]);
}
resume(c);
} int main()
{
int x1, y1, x2, y2;
int cas;
scanf("%d", &cas);
while(cas--)
{
scanf("%d%d%d", &n, &m, &p);
init(n, n*m);
for(int i = ; i <= p; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
H[i] = -;
for(int j = x1; j < x2; j++)
for(int k = y1; k < y2; k++)
ins(i, j*m+k+);
}
ans = oo;
dfs();
printf("%d\n", ans == oo ? - : ans);
}
return ;
}
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”，但显然，这是不合法的，因为一个格子只能填一个数！终于想通了啊。
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int A = ;
const int N = A*A*A+;
const int M = (A+A+A)*A+A*A+;
const int head = ;
const int oo = 0x3f3f3f3f; int U[N*M], D[N*M], L[N*M], R[N*M];
int S[N*M], O[N*M], H[N*M];
int X[N*M], Y[N*M];
int n, num, sz, len, p;
bool g[N][M];
char s[];
int ans[N][M]; void init(int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++;
D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r;
if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]];
}
}
} void resume(const int &c)
{
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
} bool dfs(const int &k)
{
if(R[head] == head)
return true; int s(oo), c;
for(int t = R[head]; t != head; t = R[t])
{
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
ans[Y[i]/][Y[i]%/] = Y[i]%+;
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
if(dfs(k+))
return true;
for(int j = L[i]; j != i; j = L[j])
resume(X[j]);
}
resume(c);
return false;
} void love(int i, int j, int k)
{
int row = (i*+j)*+k;
g[row][i*+j] = true;
g[row][*+i*+k] = true;
g[row][*+j*+k] = true;
int a = i/, b = j/;
g[row][* + (a*+b)*+k] = true;
} int main()
{
while(scanf("%s", s) != EOF)
{
if(strcmp(s, "end") == ) break;
init(A*A*);
memset(g, false, sizeof g);
memset(H, -, sizeof H);
for(int i = ; i < A; i++)
{
for(int j = ; j < A; j++)
{
if(s[i*A+j] != '.')
{
int k = s[i*A+j]-'';
love(i, j, k);
}
else
{
for(int k = ; k < A; k++)
love(i, j, k);
}
}
}
for(int i = ; i < N; i++)
for(int j = ; j < M; j++)
if(g[i][j])
ins(i, j+); // column id begin from 1, not 0, so j plus 1 dfs();
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
printf("%d", ans[i][j]);
putchar('\n');
}
return ;
}
POJ 3076 Sudoku
和POJ3074一样,只不过是16*16的数独。
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int A = ;
const int N = A*A*A+;
const int M = A*A*+;
const int head = ;
const int oo = 0x3f3f3f3f; int U[N*M], D[N*M], L[N*M], R[N*M];
int S[N*M], O[N*M], H[N*M];
int X[N*M], Y[N*M];
int n, num, sz, len, p;
bool g[N][M];
char s[][];
int ans[N][M]; void init(int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++;
D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r;
if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]];
}
}
} void resume(const int &c)
{
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
} bool dfs(const int &k)
{
if(R[head] == head)
return true; int s(oo), c;
for(int t = R[head]; t != head; t = R[t])
{
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
ans[Y[i]/(A*A)][Y[i]%(A*A)/A] = Y[i]%A;
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
if(dfs(k+))
return true;
for(int j = L[i]; j != i; j = L[j])
resume(X[j]);
}
resume(c);
return false;
} void love(int i, int j, int k)
{
int row = (i*A+j)*A+k;
g[row][i*A+j] = true;
g[row][A*A*+i*A+k] = true;
g[row][A*A*+j*A+k] = true;
int a = i/, b = j/;
g[row][A*A* + (a*+b)*A+k] = true;
} int main()
{
bool flag = false;
while(scanf("%s", s[]) != EOF)
{
for(int i = ; i < A; i++)
scanf("%s", s[i]);
if(flag) putchar('\n');
flag = true;
init(A*A*);
memset(g, false, sizeof g);
memset(H, -, sizeof H);
for(int i = ; i < A; i++)
{
for(int j = ; j < A; j++)
{
if(s[i][j] != '-')
{
int k = s[i][j] -'A';
love(i, j, k);
}
else
{
for(int k = ; k < A; k++)
love(i, j, k);
}
}
}
for(int i = ; i < N; i++)
for(int j = ; j < M; j++)
if(g[i][j])
ins(i, j+); dfs();
for(int i = ; i < A; i++)
{
for(int j = ; j < A; j++)
putchar(ans[i][j]+'A');
putchar('\n');
}
}
return ;
}
POJ2676 HDU2780 HDU3111 都是差不多的，不提。
HDU 3909 Sudoku
这道题总的来说是简单的，弄清题意就行。这道题我对DLX解数独更进一步了解了，在dfs函数中，要想得到一个解，那么必须在找到一个解的时候return true，如果不设返回值，那么得到的解会被后面的继续深搜覆盖掉，所以要及时返回。如果想知道是否有多个解，那么，可以新建变量cnt进行计数。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii pair<int,int>
#define clr(a) memset((a),0,sizeof (a))
#define rep(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(a);i>=(int)(b);i--)
#define oo 0x3f3f3f3f
#define eps 1e-6
#define N (16*16*16+5)
#define M (16*16*4+5)
#define mod 1000000007
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&x)
#define RII(x,y) scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL; const int head = ; int A;
int U[N*M], D[N*M], L[N*M], R[N*M];
int S[N*M], O[N*M], H[N*M];
int X[N*M], Y[N*M];
int n, num, sz, len, p;
bool g[N][M];
char s[][];
int ans[][], b[][], cnt; void init(int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++;
D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r;
if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]];
}
}
} void resume(const int &c)
{
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
} bool dfs(const int &k, bool f)
{
if(R[head] == head)
{
if(cnt || f)
{
cnt++;
return true;
}
cnt++;
return false;
}
int s(oo), c;
for(int t = R[head]; t != head; t = R[t])
{
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
ans[Y[i]/(A*A)][Y[i]%(A*A)/A] = Y[i]%A+;
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
if(dfs(k+, f)) return true;
for(int j = L[i]; j != i; j = L[j])
resume(X[j]);
}
resume(c);
return false;
} void love(int i, int j, int k)
{
int row = (i*A+j)*A+k;
g[row][i*A+j] = true;
g[row][A*A*+i*A+k] = true;
g[row][A*A*+j*A+k] = true;
int p = (int)sqrt(A);
int a = i/p, b = j/p;
g[row][A*A* + (a*p+b)*A+k] = true;
} void solve()
{
cnt = ;
init(A*A*);
memset(g, false, sizeof g);
memset(H, -, sizeof H);
for(int i = ; i < A; i++)
{
for(int j = ; j < A; j++)
{
if(s[i][j] != '.')
{
int k;
if(s[i][j] >= '' && s[i][j] <= '') k = s[i][j] - '';
else k = s[i][j] - 'A' + ;
love(i, j, k);
}
else
{
for(int k = ; k < A; k++)
love(i, j, k);
}
}
}
for(int i = ; i < N; i++)
{
for(int j = ; j < M; j++)
{
if(g[i][j])
ins(i, j+);
}
}
} int main()
{
while(RI(A) != EOF)
{
A = A * A;
rep(i,,A-)
scanf("%s", s[i]);
solve();
dfs(, );
if(cnt == )
{
puts("No Solution");
continue;
}
else if(cnt > )
{
puts("Multiple Solutions");
continue;
}
for(int i = ; i < A; i++)
{
for(int j = ; j < A; j++)
{
if(s[i][j] != '.')
{
char c = s[i][j];
s[i][j] = '.';
solve();
dfs(, );
if(cnt < )
goto end ;
s[i][j] = c;
}
}
}
solve();
dfs(, );
for(int i = ; i < A; i++)
{
for(int j = ; j < A; j++)
{
if(ans[i][j] <= )
printf("%d", ans[i][j]);
else
printf("%c", ans[i][j]-+'A');
}
putchar('\n');
}
continue;
end:
puts("Not Minimal");
}
return ;
}
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行，表示如果某个城市选择了一个区间，就锁定该城市。还要注意重边情况。
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = ;
const int M = ;
const int oo = 0x3f3f3f3f; int U[N*M], D[N*M], L[N*M], R[N*M];
int S[N*M], O[N*M], H[N*M];
int X[N*M], Y[N*M];
int n, m, d, num, sz, len, p;
int g[N][M]; int hh[][]; struct Node
{
int s, e;
}ans[N]; void init(int m)
{
for(int i = ; i <= m; i++)
{
U[i] = D[i] = i;
L[i+] = i;
R[i] = i+;
S[i] = ;
}
R[m] = ;
L[] = m;
sz = m+;
} void ins(int r, int c)
{
S[c]++;
D[U[c]] = sz;
U[sz] = U[c];
D[sz] = c;
U[c] = sz;
X[sz] = c;
Y[sz] = r;
if(H[r] == -)
H[r] = L[sz] = R[sz] = sz;
else
{
R[L[H[r]]] = sz;
L[sz] = L[H[r]];
R[sz] = H[r];
L[H[r]] = sz;
}
sz++;
} void remove(const int &c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[X[j]];
}
}
} void resume(const int &c)
{
for(int i = D[c]; i != c; i = D[i])
{
for(int j = R[i]; j != i; j = R[j])
{
++S[X[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
} bool dfs(const int &k)
{
if(R[] == )
{
O[k] = -;
return true;
}
int s(oo), c;
for(int t = R[]; t != ; t = R[t])
{
if(S[t] < s)
{
s = S[t];
c = t;
}
}
remove(c);
for(int i = D[c]; i != c; i = D[i])
{
O[k] = Y[i];
for(int j = R[i]; j != i; j = R[j])
remove(X[j]);
if(dfs(k+))
return true;
for(int j = L[i]; j != i; j = L[j])
resume(X[j]);
}
resume(c);
return false;
} int main()
{
int a, b;
while(scanf("%d%d%d", &n, &m, &d) != EOF)
{
memset(hh, , sizeof hh);
memset(g, , sizeof g);
memset(H, -, sizeof H);
for(int i = ; i < m; i++)
{
scanf("%d%d", &a, &b);
hh[a][b] = hh[b][a] = ;
}
init(d*n+n);
for(int i = ; i < n; i++)
{
scanf("%d%d", &a, &b);
for(int j = a-; j < b; j++)
{
for(int k = j; k < b; k++)
{
for(int u = j; u <= k; u++)
{
g[i*+j*+k][u*n+i+] = ;
g[i*+j*+k][d*n+i+] = ;
for(int v = ; v <= n; v++)
if(hh[i+][v])
g[i*+j*+k][u*n+v] = ;
}
}
}
}
for(int i = ; i < n; i++) // 每个城市的[0,0]区间
g[*n+i][d*n+i+] = ;
for(int i = ; i < n*+n; i++)
for(int j = ; j <= d*n+n; j++)
if(g[i][j]) ins(i, j); if(!dfs())
puts("No solution\n");
else
{
memset(ans, , sizeof ans);
for(int i = ; O[i] != -; i++)
{
if(O[i] >= *n) continue;
ans[O[i]/+].s = O[i]%/+;
ans[O[i]/+].e = O[i]%+;
}
for(int i = ; i <= n; i++)
printf("%d %d\n", ans[i].s, ans[i].e);
putchar('\n');
}
}
return ;
}
最新文章
- 排列组合算法的javascript实现
- java数组引用
- 分享google的技能的11个级别，大家看看自己到哪个级别了？
- 2016HUAS_ACM暑假集训3B - Frogger
- Android自动化学习笔记之MonkeyRunner：MonkeyRunner环境搭建
- html() 和 text() 方法的区别
- Android UI 优化——使用HierarchyViewer工具
- Power-BI这些饼图你用过吗
- GoldenGate 之 Bounded Recovery说明
- UIkit框架之UIalert(iOS 9之后就不用这个了)
- Struts2中将.action改为.do
- CSS3 制作向左、向右及关闭图标的效果 (另一种思路)
- 从0开始LInux配置PHP开发环境
- APUE-文件和目录（三）函数chown 和lchown
- 树莓派.安装Samba环境
- 03.redis与ssm整合（mybatis二级缓存）
- node基础—http模块
- cut语法
- Spark性能优化指南——高级篇
- 这才是真正的裸眼3D！超级震撼！！