首页 > 代码库 > SPOJ 1771&&DLX精确覆盖，重复覆盖
SPOJ 1771&&DLX精确覆盖，重复覆盖
DLX的题，做过这题才算是会吧。
这道题转化成了精确覆盖模型来做，一开始，只是单纯的要覆盖完行列和斜线，WA。
后来醒悟了，不能这样，只要覆盖全部行或列即可。虽然如此，但某些细节地方很关键不能考虑到。
特别要注意的是
for(int i=R[c];i;i=R[i]){ if(i>ne) break; if(S[i] < S[c]) c = i;}找最小值只能是在ne之前，为什么呢？因为我们要完全覆盖行。可行吗？可行。稍微留意一下DLX的模板就知道，它其实在选中一列之后，是会枚举列上的行值，
也就是说，该列（代表棋盘某一行）的每一个们置都会考虑到，不必担心无解。
DLX这个算法很巧妙啊，其实它只是一种高效的剪枝吧。妙妙妙，做过这题后才算真正懂得这个算法。
#include<cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn=500;const int maxnode=500*2500;int ne;int anst[maxn];struct DLX{ int n , sz; // 行数，节点总数 int S[maxn]; // 各列节点总数 int row[maxnode],col[maxnode]; // 各节点行列编号 int L[maxnode],R[maxnode],U[maxnode],D[maxnode]; // 十字链表 int ansd,ans[maxn]; // 解 void init(int n ) { this->n = n ; for(int i = 0 ; i <= n; i++ ) { U[i] = i ; D[i] = i ; L[i] = i - 1; R[i] = i + 1; } R[n] = 0 ; L[0] = n; sz = n + 1 ; memset(S,0,sizeof(S)); } void addRow(int r,vector<int> c1) { int first = sz; for(int i = 0 ; i < c1.size(); i++ ){ int c = c1[i]; L[sz] = sz - 1 ; R[sz] = sz + 1 ; D[sz] = c ; U[sz] = U[c]; D[U[c]] = sz; U[c] = sz; row[sz] = r; col[sz] = c; S[c] ++ ; sz ++ ; } R[sz - 1] = first ; L[first] = sz - 1; } // 顺着链表A，遍历除s外的其他元素 #define FOR(i,A,s) for(int i = A[s]; i != s ; i = A[i]) void remove(int c){ L[R[c]] = L[c]; R[L[c]] = R[c]; FOR(i,D,c) FOR(j,R,i) {U[D[j]] = U[j];D[U[j]] = D[j];--S[col[j]];} } void restore(int c){ FOR(i,U,c) FOR(j,L,i) {++S[col[j]];U[D[j]] = j;D[U[j]] = j; } L[R[c]] = c; R[L[c]] = c; } bool dfs(int d){ if(d >= ne ){ ansd=d; for(int i=0;i<ne;i++){ int x=(ans[i]-1)/ne+1; int y=(ans[i]-1)%ne+1; anst[x]=y; } printf("%d",anst[1]); for(int i=2;i<=ne;i++) printf(" %d",anst[i]); printf("\n"); return true; } // 找S最小的列c int c = R[0] ; for(int i=R[c];i;i=R[i]){ if(i>ne) break; if(S[i] < S[c]) c = i;} remove(c); FOR(i,D,c){ ans[d] = row[i]; FOR(j,R,i) remove(col[j]); if(dfs(d + 1)) return true; FOR(j,L,i) restore(col[j]); } restore(c); return false; } void solve(){ dfs(0); }};DLX solver;int puzzle[100][100];int main(){ int tmp; while(scanf("%d",&ne)!=EOF){ memset(puzzle,0,sizeof(puzzle)); for(int k=1;k<=ne;k++){ scanf("%d",&tmp); if(tmp>0){ for(int i=1;i<=ne;i++) puzzle[k][i]=puzzle[i][tmp]=-1; for(int i=1;k-i>0&&tmp-i>0;i++) puzzle[k-i][tmp-i]=-1; for(int i=1;k+i<=ne&&tmp+i<=ne;i++) puzzle[k+i][tmp+i]=-1; for(int i=1;k-i>0&&tmp+i<=ne;i++) puzzle[k-i][tmp+i]=-1; for(int i=1;k+i<=ne&&tmp-i>0;i++) puzzle[k+i][tmp-i]=-1; puzzle[k][tmp]=1; } } solver.init(6*ne-2); vector<int>columns; for(int i=1;i<=ne;i++){ for(int j=1;j<=ne;j++){ columns.clear(); if(puzzle[i][j]>=0){ columns.push_back(i); columns.push_back(ne+j); columns.push_back(ne*2+j-1+i); columns.push_back(ne*2+2*ne-1+ne-i+j); solver.addRow((i-1)*ne+j,columns); } } } solver.solve(); } return 0;}
摘http://www.cnblogs.com/jh818012/p/3252154.html
重复覆盖模板
const int maxn=360000;const int maxc=500;const int maxr=500;const int inf=0x3f3f3f3f;int L[maxn], R[maxn], D[maxn], U[maxn], C[maxn];int S[maxc], H[maxr], size;///不需要S域void Link(int r, int c){ S[c]++; C[size]=c; U[size]=U[c]; D[U[c]]=size; D[size]=c; U[c]=size; if(H[r]==-1) H[r]=L[size]=R[size]=size; else { L[size]=L[H[r]]; R[L[H[r]]]=size; R[size]=H[r]; L[H[r]]=size; } size++;}void remove(int c){ for (int i=D[c]; i!=c; i=D[i]) L[R[i]]=L[i], R[L[i]]=R[i];}void resume(int c){ for (int i=U[c]; i!=c; i=U[i]) L[R[i]]=R[L[i]]=i;}int h(){///用精确覆盖去估算剪枝 int ret=0; bool vis[maxc]; memset (vis, false, sizeof(vis)); for (int i=R[0]; i; i=R[i]) { if(vis[i])continue; ret++; vis[i]=true; for (int j=D[i]; j!=i; j=D[j]) for (int k=R[j]; k!=j; k=R[k]) vis[C[k]]=true; } return ret;}int ans;void Dance(int k){ //根据具体问题选择限制搜索深度或直接求解。 A*算法，此处只求最优解 if(k+h()>=ans) return; if(!R[0]){ if(k<ans)ans=k; return; } int c=R[0]; for (int i=R[0]; i; i=R[i]) if(S[i]<S[c])c=i; for (int i=D[c]; i!=c; i=D[i]){ remove(i); for (int j=R[i]; j!=i; j=R[j]) remove(j); Dance(k+1); for (int j=L[i]; j!=i; j=L[j]) resume(j); resume(i); } return ;}void initL(int x){///col is 1~x,row start from 1 for (int i=0; i<=x; ++i){ S[i]=0; D[i]=U[i]=i; L[i+1]=i; R[i]=i+1; }///对列表头初始化 R[x]=0; size=x+1;///真正的元素从m+1开始 memset (H, -1, sizeof(H)); ///mark每个位置的名字} DLX 重复覆盖 template
精确覆盖模板
struct DLX{ int n , sz; // 行数，节点总数 int S[maxn]; // 各列节点总数 int row[maxnode],col[maxnode]; // 各节点行列编号 int L[maxnode],R[maxnode],U[maxnode],D[maxnode]; // 十字链表 int ansd,ans[maxn]; // 解 void init(int n ) { this->n = n ; for(int i = 0 ; i <= n; i++ ) { U[i] = i ; D[i] = i ; L[i] = i - 1; R[i] = i + 1; } R[n] = 0 ; L[0] = n; sz = n + 1 ; memset(S,0,sizeof(S)); } void addRow(int r,vector<int> c1) { int first = sz; for(int i = 0 ; i < c1.size(); i++ ){ int c = c1[i]; L[sz] = sz - 1 ; R[sz] = sz + 1 ; D[sz] = c ; U[sz] = U[c]; D[U[c]] = sz; U[c] = sz; row[sz] = r; col[sz] = c; S[c] ++ ; sz ++ ; } R[sz - 1] = first ; L[first] = sz - 1; } // 顺着链表A，遍历除s外的其他元素 #define FOR(i,A,s) for(int i = A[s]; i != s ; i = A[i]) void remove(int c){ L[R[c]] = L[c]; R[L[c]] = R[c]; FOR(i,D,c) FOR(j,R,i) {U[D[j]] = U[j];D[U[j]] = D[j];--S[col[j]];} } void restore(int c){ FOR(i,U,c) FOR(j,L,i) {++S[col[j]];U[D[j]] = j;D[U[j]] = j; } L[R[c]] = c; R[L[c]] = c; } bool dfs(int d){ if(R[0] == 0 ){ ansd = d; return true; } // 找S最小的列c int c = R[0] ; FOR(i,R,0) if(S[i] < S[c]) c = i; remove(c); FOR(i,D,c){ ans[d] = row[i]; FOR(j,R,i) remove(col[j]); if(dfs(d + 1)) return true; FOR(j,L,i) restore(col[j]); } restore(c); return false; } bool solve(vector<int> & v){ v.clear(); if(!dfs(0)) return false; for(int i = 0 ; i< ansd ;i ++ ) v.push_back(ans[i]); return true; }};DLX solver;int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { solver.init(m); int c , x; vector<int> c1; for(int i = 1; i<= n ; i ++ ) { scanf("%d",&c); c1.clear(); for(int j = 0 ; j < c ; j ++ ){scanf("%d",&x);c1.push_back(x);} solver.addRow(i,c1); } vector<int> ans; bool flag ; flag = solver.solve(ans); if(flag ) { int size1 = ans.size(); printf("%d",size1); for(int i = 0 ; i < size1;i ++ ) printf(" %d",ans[i]); printf("\n"); } else printf("NO\n"); } return 0;}
SPOJ 1771&&DLX精确覆盖，重复覆盖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。