• 精确覆盖问题
• 使用 dancing links
• 本质思想是十字链表

// P4929 模板 舞蹈链 DLX
#include<iostream>
#include<cstdio>
#define MAXN 510
#define MAXM 510
#define MAX (MAXN*MAXM)
using namespace std;
int n,m;
struct DLX{int n,m,sz; // n为行数，m为列数，sz表示总节点数int U[MAX],D[MAX],R[MAX],L[MAX],row[MAX],col[MAX];int H[MAXN],S[MAXM];int res[MAXN];void init(int _n,int _m){n=_n;m=_m;for(int i=0;i<=m;i++){ // 每一列先创建一个结点// 编号 [0,m] 表示每一列的表头S[i]=0; // S[i] 表示 i 列的元素个数，初始化为 0U[i]=D[i]=i; // U 表示上方，D 表示下方，形成双向链表L[i]=i-1; // i 的左边是 i-1R[i]=i+1; // i 的右边是 i+1}R[m]=0;L[0]=m; // 形成循环链表，m 的右边是 0，0 的左边是 msz=m; // sz 用来对结点进行编号for(int i=1;i<=n;i++)H[i]=-1; // H[i] 表示第i行第一个元素编号}void link(int r,int c){// row,col 表示结点所在的行和列++S[col[++sz]=c]; // 添加新的结点，col 表示该结点所在的列row[sz]=r; // row 表示新结点所在的行D[sz]=D[c]; // 链表操作U[D[c]]=sz; // 这四步U[sz]=c;    // 将新结点插入到D[c]=sz;    // 列链表上// 以下操作：将新结点插入到行链表上// 首先判断该行上是否有结点if(H[r]<0)H[r]=L[sz]=R[sz]=sz;else{ // 以下操作是将新结点插入到该行第一个结点右边R[sz]=R[H[r]];L[R[sz]]=sz;L[sz]=H[r];R[L[sz]]=sz;}}void remove(int c){ // 去掉c列L[R[c]]=L[c];R[L[c]]=R[c]; // 首先把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])++S[col[U[D[j]]=D[U[j]]=j]];L[R[c]]=R[L[c]]=c;}bool dance(int d){if(R[0]==0){for(int i=0;i<d;i++)printf("%d ",res[i]);return true;}int c=R[0]; // 选择元素个数最少的那一列开始去for(int i=R[0];i!=0;i=R[i])if(S[i]<S[c]) // S[i] 表示 i 列的元素个数c=i;remove(c); // 将i列去掉for(int i=D[c];i!=c;i=D[i]){res[d]=row[i];for(int j=R[i];j!=i;j=R[j])remove(col[j]);if(dance(d+1))return true;for(int j=L[i];j!=i;j=L[j])resume(col[j]);}resume(c);return false;}
};int main(){
#ifdef WINEfreopen("data.in","r",stdin);
#endifDLX d;scanf("%d%d",&n,&m); // n 行 m 列d.init(n,m);for(int i=0;i<n;i++)for(int j=0;j<m;j++){int k;scanf("%d",&k);if(k)d.link(i+1,j+1); // i,j 处进行连接}if(!d.dance(0))printf("No Solution!\n");return 0;
}