跳舞链 学习笔记

## 跳舞链用来干什么 用来解决 `精准覆盖` 问题。 通常所说的跳舞链，其实是指 `DLX (Dancing Links 优化的 X 算法)` ## DLX讲解 [这篇](https://leverimmy.blog.luogu.org/dlx-xiang-xi-jiang-jie)讲得很好。 ~~主要因为自己懒得写~~ ## 模板 - [P4929 【模板】舞蹈链（DLX）](https://www.luogu.com.cn/problem/P4929) ```cpp #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fo2(v,a,b) for(v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define fe(v,a) for(int v=head[a];v;v=Next[v]) #define rg register #define il inline #define dlx(i,A,x) for(int i=A[x];i!=x;i=A[i]) const int RN=510,N=25010; int n,m,a[RN][RN],cnt; int L[N],R[N],U[N],D[N]; //这里的L,R,U,D都是循环的，即最后一个数的后一个就是第一个 int siz[N],fir[N],col[N],row[N]; //fir是每行的第一个元素，siz是每列的元素个数 //row--行 col--列 void build()//初始化一个Dancing Links，并未赋值 { fo(i,0,m) { L[i]=i-1,R[i]=i+1; U[i]=D[i]=i; } L[0]=m,R[m]=0;cnt=m; } void remove(int x)//删第x列 { L[R[x]]=L[x],R[L[x]]=R[x];//先从链表中删第x列 dlx(i,D,x)//该列之下的有1的行 dlx(j,R,i)//该行中有1的地方 { U[D[j]]=U[j],D[U[j]]=D[j];//删第j个数 siz[col[j]]--;//维护siz数组 } } void recover(int x)//恢复第x列，操作顺序恰与remove相反 { dlx(i,U,x) dlx(j,L,i) {//同上 U[D[j]]=D[U[j]]=j; siz[col[j]]++; } L[R[x]]=R[L[x]]=x; } void link(int r,int c)//新增一个(r,c)的节点，OI-Wiki中是insert { cnt++;//开始插入一个新节点cnt col[cnt]=c,row[cnt]=r,siz[c]++;//维护基本信息 D[cnt]=D[c],U[D[c]]=cnt,U[cnt]=c,D[c]=cnt;//维护列信息 if(!fir[r])//该行没有元素 fir[r]=L[cnt]=R[cnt]=cnt; else//在fir[r]之后插入 { L[cnt]=fir[r],R[cnt]=R[fir[r]]; L[R[fir[r]]]=cnt,R[fir[r]]=cnt; } } vector<int> ans; bool dance(int now) { if(!R[0])return true;//当前Dancing Links为空，成功 int c=R[0]; dlx(i,R,0) if(siz[i]<siz[c]) c=i;//取列元素个数最少的一列 remove(c);//将其删去 dlx(i,D,c)//遍历c一行的所有元素 { ans.push_back(row[i]);//将当前行记录下来 dlx(j,R,i)remove(col[j]); if(dance(now+1))return true; dlx(j,L,i)recover(col[j]); ans.pop_back(); } recover(c); return false; } int main() { cin>>n>>m; build(); fo(i,1,n) fo(j,1,m) { scanf("%d",&a[i][j]); if(a[i][j])link(i,j); } if(dance(1)) fo(i,0,(int)ans.size()-1) printf("%d ",ans[i]); else puts("No Solution!"); return 0; } ```