首页 > 代码库 > DancingLinks刷题集
DancingLinks刷题集
HDU 3663 Power Stations 精确覆盖
题意：每个城市i有xi->yi天可以成为发射站，发射站覆盖范围为与该站有一条边链接的城市。
同时，每个每天城市必须且只能被一个发射站覆盖
天数D<=5。 每个城市的发射站关闭后就不再开启。即只能选择一段区间。
问若能做到，则输出每个城市开启时间与关闭时间
否则输出No solution
做法：
1.天数城市可独立看待，故每个城市每天看做一列。
2.在此区间内取一段子区间，注意到D很小，可枚举起点时刻终点时刻，每个城市每个方案作为一行。
3.对每个方案可覆盖到的城市及各天，则对该行该列设1
4.为解决每个城市只能取一段区间，则对每个城市设置一个新的列，该城市所有方案在该列设1，使不重复选择。
5.注意设置每个城市发射站未开启的方案行。因为不开是可行的。6。
注意多输出一行空行
//2014.11.7
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;#define N 1004#define M 850#define T 820000#define INF 0x3f3f3f3fvector<int>vec[66];int dir[10];bool g[66][66];vector<int>v;struct Day{ int x,y; Day(){}; Day(int xx, int yy): x(xx), y(yy){};}p[66], ans[66], rec[N];int yingying, f[N];void dabiao(){ int i; dir[0] = 0; for(i = 1; i <= 5; i++) dir[i] = i + dir[i-1];}struct DLX{ int L[T], R[T], U[T], D[T]; int head[N]; int cnt[M], col[T], row[T], id, n, m; void init(int nn, int mm){ this->n = nn; this->m = mm; int i; for(i = 0; i <= m; i++){ D[i] = U[i] = i; L[i] = i-1; R[i] = i + 1; } id = m + 1; R[m] = 0; L[0] = m; memset(cnt, 0, sizeof(cnt)); memset(head, -1, sizeof(head)); } void add(int r, int c){ D[id] = c; U[id] = U[c]; D[U[c]] = id; U[c] = id; if(head[r] < 0 ){ head[r] = L[id] = R[id] = id; } else { L[id] = head[r]; R[id] = R[head[r]]; L[R[head[r]]] =id; R[head[r]] = id; head[r] = id; } cnt[c] ++; col[id] = c; row[id] =r; id ++; } void del(int x){ int i, j; L[R[x]] = L[x]; R[L[x]] = R[x]; for(i = D[x]; i != x; i = D[i]){ for(j = R[i]; j != i; j = R[j]){ cnt[col[j]] --; U[D[j]] = U[j]; D[U[j]] = D[j]; } } } void resume(int x){ int i, j; for(i = U[x]; i != x; i = U[i]){ for(j = L[i]; j != i; j = L[j]){ cnt[col[j]] ++; D[U[j]] = j; U[D[j]] = j; } } L[R[x]] = x; R[L[x]] = x; } bool dfs(){ if(R[0] == 0) return true; int idx , temp, i, j; temp = INF; for(i = R[0]; i != 0; i = R[i]){ if(cnt[i] < temp){ temp = cnt[i]; idx = i; } } if(temp == 0) return false; del(idx); for(i = D[idx]; i != idx; i = D[i]){ Day tttt = ans[f[row[i]]]; ans[f[row[i]]] = rec[row[i]]; for(j = R[i]; j != i; j = R[j]){ del(col[j]); } if(dfs()) return true; for(j = L[i]; j != i; j = L[j]){ resume(col[j]); } ans[f[row[i]]] = tttt; } resume(idx); return false; }}dlx;bool gao(int n, int d){ int sum = 0, i, j, k, t, tt; for(i = 1; i <= n; i++){ sum += dir[p[i].y - p[i].x]; } dlx.init(sum, n * d + n); sum = 0; for(i = 1; i <= n; i++){ for(j = p[i].x; j <= p[i].y; j++){ for(k = j; k <= p[i].y; k++){ ++sum; for(tt = 0; tt < vec[i].size(); tt++){ for(t = j; t <= k; t++){ dlx.add(sum, (vec[i][tt]-1)*d+t); } } dlx.add(sum, n * d +i); rec[sum] = Day(j, k); f[sum] = i; } } } for(i = 1; i <= n; i ++){ dlx.add(++sum, n * d + i); f[sum] = n + 1; } return dlx.dfs();}int main(void){ int n, m, d, i, j, x, y; dabiao(); while(scanf("%d%d%d", &n, &m, &d) != EOF){ fill(vec, vec+66, vector<int>() ); memset(g, false, sizeof(g)); while(m--){ scanf("%d%d", &x, &y); if(g[x][y]) continue; g[x][y] = g[y][x] = true; vec[x].push_back(y); vec[y].push_back(x); } for(i = 1; i <= n; i++){ scanf("%d%d", &p[i].x, &p[i].y); vec[i].push_back(i); ans[i] = Day(0, 0); } yingying = n; if(gao(n, d)){ for(i = 1; i <= n; i++){ printf("%d %d\n", ans[i].x, ans[i].y); } } else printf("No solution\n"); printf("\n"); } return 0;}
HDU 2828 Lamp
重复覆盖+判断冲突
题意：有N盏灯可以由M个开关控制，对于第i盏灯，当条件A|| B || C。。。满足则灯亮，条件X为j开关OFF或ON状态。
问开关处于何种状态时，灯是全开的。SPJ
做法：
建图的第一部分很简单，以N盏灯为列，每个开关的开/关状态各为一行，对处于此状态为亮的灯为1.
然后是开关的状态只能取一个的解决方法。对于每个开关状态on / off是否采用，设置vis数组，若dfs时对应的另一个状态已经采用，则此状态非法，不搜。
以上，可解决。
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;#define N 1004#define T 1000004#define INF 0x3f3f3f3fint f[N][N>>1], ans[504];vector<int>v;int M ;struct DLX{ int r[T], l[T], u[T], d[T]; int cnt[N], col[T], row[N], head[N]; bool vis[N]; int n, id; void init(int n){ this->n = n; int i; for(i = 0; i <= n; i++){ d[i] = u[i] = i; l[i] = i - 1; r[i] = i + 1; } id = n + 1; r[n] = 0; l[0] = n; memset(cnt, 0, sizeof(cnt)); memset(vis, false, sizeof(vis)); memset(head, -1, sizeof(head)); } void add(int R, int C){ d[id] = C; u[id] = u[C]; d[u[C]] = id; u[C] = id; if(head[R] < 0 ){ head[R] = l[id] = r[id] = id; } else { l[id] = head[R]; r[id] = r[head[R]]; l[r[head[R]]] =id; r[head[R]] = id; head[R] = id; } cnt[C] ++; col[id] = C; row[id] =R; id ++; } void remove(int x){ int i; for(i = u[x]; i != x; i = u[i]){ l[r[i]] = l[i]; r[l[i]] = r[i]; } } void resume(int x){ int i; for(i = d[x]; i != x; i = d[i]){ l[r[i]] = i; r[l[i]] = i; } } bool dfs(){ if(r[0] == 0) return true; int i, c = r[0], j; for(i = r[0]; i != 0; i = r[i]){ if(cnt[i] <cnt[c]) c = i; } for(i = d[c]; i != c; i = d[i]){ if(vis[row[i]^1] ) continue; vis[row[i]] = true; remove(i); for(j = r[i]; j != i; j = r[j]){ remove(j); } if(dfs()) return true; for(j = l[i]; j != i; j = l[j]) resume(j); resume(j); resume(i); vis[row[i]] = false; } return false; }}dlx;bool gao(int n, int m){ dlx.init(n); m <<= 1; int i, j; for(i = 0; i < m; i++){ for(j = 1; j <= n; j++){ if(f[i][j]){ dlx.add(i, j); } } } return dlx.dfs();}int main(){ int n, m, i, k, x; char op[10]; while(scanf("%d%d", &n, &m) != EOF){ memset(f, 0, sizeof(f)); M = n; for(i = 1; i <= n; i++){ scanf("%d", &k); while(k--){ scanf("%d%s", &x, op); x--; if(op[1] == ‘N‘){ f[x<<1][i] = 1; } else f[x<<1|1][i] = 1; } } if(gao(n, m)){ for(i = 0; i < m; i++){ printf("%s%c", dlx.vis[i<<1] ? "ON": "OFF", i == m - 1? ‘\n‘ : ‘ ‘); } } else printf("-1\n"); } return 0;}
DancingLinks刷题集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。