舞蹈链(DLX)模板

const int N=1e3+100;//行数const int M=1e3+100;//列数const int NODE=5e5+100;//节点数struct DancingLink{int n,s,ansd;//列数 节点总数 int S[M],A[N],H[N];//S[]该列节点总数 A[]答案 H[]行首指针 int L[NODE],R[NODE],U[NODE],D[NODE]; //L[],R[],U[],D[] 上下左右 int X[NODE],C[NODE];//X[] C[] 行列编号 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;s=n+1;memset(S,0,sizeof(S));memset(H,-1,sizeof(H));}void DelCol(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[C[j]];}void ResCol(int c){//恢复列 for(int i=U[c];i!=c;i=U[i])for(int j=L[i];j!=i;j=L[j])++S[C[j]],U[D[j]]=j,D[U[j]]=j;L[R[c]]=c,R[L[c]]=c;}void AddNode(int r,int c){//添加节点 ++S[c],C[++s]=c,X[s]=r;D[s]=D[c],U[D[c]]=s,U[s]=c,D[c]=s;if(H[r]<0) H[r]=L[s]=R[s]=s;//行首节点else R[s]=R[H[r]],L[R[H[r]]]=s,L[s]=H[r],R[H[r]]=s;}bool dfs(int d){//深度，深搜遍历 if(!R[0]){ansd=d;return true;}int c=R[0];for(int i=R[0];i;i=R[i]) if(S[i]<S[c]) c=i;DelCol(c);for(int i=D[c];i!=c;i=D[i]){A[d]=X[i];for(int j=R[i];j!=i;j=R[j]) DelCol(C[j]);if(dfs(d+1)) return true;for(int j=L[i];j!=i;j=L[j]) ResCol(C[j]);}ResCol(c);return false;}}dlx;

 

总结

以上是生活随笔为你收集整理的舞蹈链(DLX)模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。