简述
舞蹈链用于解决精确覆盖问题
精确覆盖问题
给定许多集合 \(S_i (1 \le i \le n)\) 以及一个集合 \(X\)，求无序多元组 \((T_1, T_2, \cdots , T_m)\)满足：
\[\begin{align*} &1.\forall i, j \in [1, m],T_i\bigcap T_j = \varnothing (i \neq j) \\&2.X=\bigcup_{i=1}^{m} T_i \\&3.\forall i\in [1, m], T_i\in\{S1,S2,……,Sn\} \end{align*} \]即从\(n\)个集合\(S_i (1 \le i \le n)\)中选出\(m\)个集合\(T_i (1 \le i \le m)\)，使得\(X\)中元素出现且只出现一次
问题转化
上述问题可以转化为：给定一个 \(N\) 行 \(M\) 列的矩阵，矩阵中每个元素要么是 \(1\)，要么是 \(0\)。你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 \(j\)，在你挑选的这些行中，有且仅有一行的第 \(j\) 个元素为 \(1\)。
主要步骤
1.选择当前矩阵的一行
2.标记该行，该行元素为 \(1\) 的列，被标记的列中含 \(1\) 的行
3.删除所有标记元素，得到新矩阵。如果新矩阵为空矩阵，跳转到 \(4\) ；否则继续求解，跳转到\(1\)
4.新矩阵为空矩阵。如果删除的行全为 \(1\) ，说明得到一个解，求解结束，跳转到 \(5\)；否则说明求解失败，跳转到 \(6\)
5.求解结束，得到一个解。
6.求解失败，回溯到上一个矩阵，选择下一行，跳转到 \(1\) 。如果没有矩阵可以回溯，说明本题无解，跳转到 \(7\)
7.求解结束，本题无解
code
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
} using namespace Q;
cs int N=505;
namespace DLX{
namespace cross_list{
struct qwq{
int l,r,u,d,ro,co;
}lst[N*12];
int row[N],ccnt[N],cnt;
il void init(cs int m){
for(ri int i=0;i<=m;++i) lst[i]={i-1,i+1,i,i,0,i};
return lst[0].l=m,lst[m].r=0,cnt=m,void();
}
il void add(cs int rw,cs int cl){
lst[++cnt].ro=rw,lst[cnt].co=cl;
lst[cnt].u=lst[cl].u,lst[lst[cnt].u].d=cnt;
lst[cnt].d=cl,lst[lst[cnt].d].u=cnt;
if(!row[rw]) lst[cnt].l=lst[cnt].r=row[rw]=cnt;
else{
lst[cnt].l=lst[row[rw]].l,lst[lst[cnt].l].r=cnt;
lst[cnt].r=row[rw],lst[lst[cnt].r].l=cnt;
}
return ccnt[cl]++,void();
}
il void del(cs int col){
for(ri int i=lst[col].d;i^col;i=lst[i].d){
for(ri int j=lst[i].r;j^i;j=lst[j].r){
lst[lst[j].d].u=lst[j].u;
lst[lst[j].u].d=lst[j].d;
ccnt[lst[j].co]--;
}
}
lst[lst[col].l].r=lst[col].r;
lst[lst[col].r].l=lst[col].l;
return;
}
il void res(int col){
lst[lst[col].l].r=lst[lst[col].r].l=col;
for(ri int i=lst[col].d;i^col;i=lst[i].d){
for(ri int j=lst[i].r;j^i;j=lst[j].r){
lst[lst[j].d].u=lst[lst[j].u].d=j;
ccnt[lst[j].co]++;
}
}
return;
}
} using namespace cross_list;
int as[N];
il void prt(cs int dep){
for(ri int i=1;i<dep-1;++i) wt(as[i]),putchar(32);
return wt(as[dep-1]),putchar(10),void();
}
il bool dlx(int dep){
if(!lst[0].r) return prt(dep),1;
ri int col=lst[0].r;
for(ri int i=lst[0].r;i;i=lst[i].r){
if(ccnt[i]<ccnt[col]) col=i;
}
del(col);
for(ri int i=lst[col].d,j;i^col;i=lst[i].d){
as[dep]=lst[i].ro;
for(j=lst[i].r;j^i;j=lst[j].r) del(lst[j].co);
if(dlx(dep+1)) return 1;
for(j=lst[i].r;j^i;j=lst[j].r) res(lst[j].co);
}
return res(col),0;
}
} using namespace DLX;
signed main(){
int n=rd(),m=rd();
init(m);
for(ri int i=1;i<=n;++i){
for(ri int j=1;j<=m;++j){
if(rd()) add(i,j);
}
}
if(!dlx(1)) puts("No Solution!");
return 0;
}