DLX模板

本文主要是介绍DLX模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DLX，Dancing Links X算法，用于求解精确覆盖问题

《算法竞赛入门经典——训练指南》P406有很好的介绍

这些博客写得也不错

http://www.cnblogs.com/grenet/p/3145800.html

http://blog.csdn.net/sunny606/article/details/7833551

struct DLX
{int n,sz;//列数，结点数int S[maxc];//各列结点数int row[maxnode],col[maxnode];//各点行列编号int L[maxnode],R[maxnode],U[maxnode],D[maxnode];//十字链表int ansd,ans[maxr];//解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);}//插入决策行  _r 行号  columns 记录结点列号·[1,n]void add_row(int _r,vector<int> columns){int first=sz;for (int i=0;i<columns.size();i++){int _c=columns[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;}//删除一列结点void _remove(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[col[j]]--;}}//恢复一列结点，和删除顺序相反void _resume(int _c){for (int i=U[_c];i!=_c;i=U[i])for (int j=L[i];j!=i;j=L[j]){U[D[j]]=j;D[U[j]]=j;S[col[j]]++;}L[R[_c]]=_c;R[L[_c]]=_c;}bool dfs(int d){if (R[0]==0){ansd=d; //记录解的长度return true;}//找最少结点的列删除int _c=R[0];for (int i=R[0];i!=0;i=R[i])if (S[i]<S[_c]) _c=i;_remove(_c);for (int i=D[_c];i!=_c;i=D[i]){ans[d]=row[i];for (int j=R[i];j!=i;j=R[j])_remove(col[j]);if (dfs(d+1))   return true;for (int j=L[i];j!=i;j=L[j])//反向恢复_resume(col[j]);}_resume(_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模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---