目录
Dancing Links
考虑这样一个问题：
给定一个 \(N\) 行 \(M\) 列的矩阵，矩阵中每个元素要么是 \(1\)，要么是 \(0\)。
你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 \(j\)，在你挑选的这些行中，有且仅有一行的第 \(j\) 个元素为 \(1\)。
这类问题统称为精确覆盖问题，我们容易得到如下所示的一个想法：
-
枚举选择一行，并将其从矩阵中删除。（不重复决策）
-
对上一步删除的行内的每个 \(1\)，将其所在列删除。（对应列为 \(1\) 的行已确定，可以剪枝）
-
对上一步删除的列内的每个 \(1\)，将其所在行删除。（避免决策出现某列有多个 \(1\) 的情形）
-
若操作后矩阵不为空，回到步骤 1。
-
若操作后矩阵为空，但最后一次决策行中元素不全为 \(1\)，回溯并回到步骤 1。
-
若操作后矩阵为空，且最后一次决策行中元素全为 \(1\)，则找到问题的一组解。
不难发现，每个 \(1\) 都是对问题的一个约束；但 \(0\) 只是对矩阵形式上的补足，缺乏实际意义。
所以在实际的精确覆盖问题中，\(0\) 的数量往往远多于 \(1\) 的数量。（以数独问题为例，一个决策中 \(0\) 的个数是数独边长的立方级，而 \(1\) 总是仅有四个）
如果直接使用二维数组模拟这个过程，每个 \(0\) 都要占据空间，空间复杂度通常很糟糕。
所以我们想到，可以用一个动态开点的数据结构，仅维护 \(1\) 的相关信息。
放心，这里并没有什么扫兴的根号和 \(\log\)，我们用链表就够了。（大概是高德纳最平易近人的想法）
对每个 \(1\)，它沿一个链表遍历过所有与它同列的 \(1\)，沿另一个链表遍历过所有与它同行的 \(1\)，也就是双向十字链表。（其实可以看成略去那些 \(0\) 之后的网格图，但首尾相接以便遍历）
剩下的其实就是对上述流程的模拟了。
DLX 模板
#include <bits/stdc++.h>
using namespace std;
const int MAXN=250007;
int n,m,cnt,ans,seq[MAXN],dcs[MAXN],sta[MAXN],siz[MAXN],first[MAXN];
int U[MAXN],D[MAXN],L[MAXN],R[MAXN];
void build()
{
for (int i=0;i<=m;i++)
{
L[i]=i-1,R[i]=i+1;
U[i]=D[i]=i;
}
L[0]=m,R[m]=0,cnt=m;
}
void ins(int d,int s)
{
cnt++,siz[s]++;
dcs[cnt]=d,sta[cnt]=s;
U[cnt]=s,D[cnt]=D[s];
U[D[s]]=cnt,D[s]=cnt;
if (!first[d]) first[d]=L[cnt]=R[cnt]=cnt;
else
{
L[cnt]=first[d],R[cnt]=R[first[d]];
L[R[first[d]]]=cnt,R[first[d]]=cnt;
}
}
void remove(int s)
{
L[R[s]]=L[s],R[L[s]]=R[s];
for (int i=D[s];i!=s;i=D[i])
for (int j=R[i];j!=i;j=R[j])
U[D[j]]=U[j],D[U[j]]=D[j],siz[sta[j]]--;
}
void recover(int s)
{
for (int i=U[s];i!=s;i=U[i])
for (int j=L[i];j!=i;j=L[j])
U[D[j]]=D[U[j]]=j,siz[sta[j]]++;
L[R[s]]=R[L[s]]=s;
}
bool dance(int dep)
{
if (!R[0])
{
ans=dep;
return 1;
}
int s=R[0];
for (int i=s;i!=0;i=R[i])
if (siz[i]<siz[s]) s=i;
remove(s);
for (int i=D[s];i!=s;i=D[i])
{
seq[dep]=dcs[i];
for (int j=R[i];j!=i;j=R[j])
remove(sta[j]);
if (dance(dep+1)) return 1;
for (int j=L[i];j!=i;j=L[j])
recover(sta[j]);
}
recover(s);
return 0;
}
int main()
{
cin>>n>>m;
build();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
int x;
cin>>x;
if (x) ins(i,j);
}
if (dance(1))
for (int i=1;i<ans;i++)
cout<<seq[i]<<' ';
else puts("No Solution!");
return 0;
}
标签：老东西,争做,删除,int,行中,矩阵,链表,算法,MAXN From： https://www.cnblogs.com/CrH2/p/18292742