精确覆盖问题の定义
精确覆盖问题（英文：Exact Cover Problem）是指给定许多集合 \(S_i (1 \le i \le n)\) 以及一个集合 \(X\)，求满足以下条件的无序多元组 \((T_1, T_2, \cdots , T_m)\)：
- \(\forall i, j \in [1, m],T_i\bigcap T_j = \varnothing (i \neq j)\)
- \(X = \bigcup\limits_{i = 1}^{m}T_i\)
- \(\forall i \in[1, m], T_i \in \{S_1, S_2, \cdots, S_n\}\)
P4929 【模板】舞蹈链（DLX）
\(My \space Code\)
#include<bits/stdc++.h>
#define il inline
#define ri register
#define pc(i) putchar(i)
#define cs const
using namespace std;
namespace zxyc
{
il void read(int &as)
{
as=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
}
void wt(int x){if(x<0) x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
}using namespace zxyc;
struct DLX{int row,col,l,r,u,d;}mp[6003];
int cnt,rowf[503],ans[503],colc[503],n,m;
//rowf每行第一个元素 colc[510]每列元素个数
il void init()
{
for(ri int i=0;i<=m;++i)
mp[i].l=i-1,mp[i].r=i+1,mp[i].u=mp[i].d=i,colc[i]=0;
mp[0].l=m,mp[m].r=0,cnt=m;
}
il void add(cs int r,cs int c)
{
//upd:col
mp[++cnt].row=r,mp[cnt].col=c,
mp[cnt].u=mp[c].u,mp[cnt].d=c,
mp[mp[cnt].u].d=cnt,mp[c].u=cnt;
//upd:row
if(!rowf[r]) mp[cnt].l=mp[cnt].r=cnt,rowf[r]=cnt;
else mp[cnt].l=mp[rowf[r]].l,mp[cnt].r=rowf[r],
mp[mp[cnt].l].r=mp[mp[cnt].r].l=cnt;
colc[c]++;
}
il void remove(cs int c)
{
for(ri int i=mp[c].d;i!=c;i=mp[i].d)
for(ri int j=mp[i].r;j!=i;j=mp[j].r)
mp[mp[j].d].u=mp[j].u,mp[mp[j].u].d=mp[j].d,colc[mp[j].col]--;
mp[mp[c].r].l=mp[c].l,mp[mp[c].l].r=mp[c].r;
}
il void resume(cs int c)
{
mp[mp[c].l].r=c,mp[mp[c].r].l=c;
for(ri int i=mp[c].d;i!=c;i=mp[i].d)
for(ri int j=mp[i].r;j!=i;j=mp[j].r)
mp[mp[j].d].u=j,mp[mp[j].u].d=j,colc[mp[j].col]++;
}
bool dance(cs int step)
{
if(mp[0].r==0)
{
for(ri int i=1;i<step;++i)
wt(ans[i]),pc(' ');
return true;
}
int C=mp[0].r;//选择列中元素最少的列
for(ri int i=mp[0].r;i;i=mp[i].r)
if(colc[i]<colc[C]) C=i;
remove(C);
for(ri int i=mp[C].d;i!=C;i=mp[i].d)
{
ans[step]=mp[i].row;
for(ri int j=mp[i].r;j!=i;j=mp[j].r)
remove(mp[j].col);
if(dance(step+1)) return true;
for(ri int j=mp[i].r;j!=i;j=mp[j].r)
resume(mp[j].col);
}
return resume(C),false;
}
signed main()
{
read(n),read(m),init();
for(ri int i=1;i<=n;++i)
for(ri int j=1,x;j<=m;++j)
{read(x);if(x) add(i,j);}
if(!dance(1)) puts("No Solution!");
return 0;
}