正題

題目鏈接:https://www.luogu.com.cn/problem/P4929

---

題目大意

$n?m$的矩形有$0/1$，要求選出若干行使得每一列有且僅有一個(gè)$1$。

---

解題思路

精確覆蓋問題指的是一個(gè)集合$S$和它的若干個(gè)子集集合$T$，要求選出$T$的一個(gè)子集使得里面的集合元素剛好覆蓋集合$S$。
$DLX$全稱是$dancinglinkX$，其中$dancinglink$是指交叉十字循環(huán)雙向鏈，$X$是指暴搜。

知道了這些，就可以去看洛谷題解了（

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10100; int n,m,cnt,l[N],r[N],u[N],d[N],h[N],row[N],col[N],s[N],ans[N]; void init(){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 link(int x,int y){col[++cnt]=y;s[y]++;d[cnt]=y;u[cnt]=u[y];d[u[y]]=cnt;u[y]=cnt;row[cnt]=x;if(!h[x])h[x]=l[cnt]=r[cnt]=cnt;else{l[cnt]=l[h[x]];r[cnt]=h[x];r[l[h[x]]]=cnt;l[h[x]]=cnt;}return; } void remove(int x){r[l[x]]=r[x];l[r[x]]=l[x];for(int i=d[x];i!=x;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]]--;return; } void recover(int x){for(int i=u[x];i!=x;i=u[i])for(int j=l[i];j!=i;j=l[j])u[d[j]]=d[u[j]]=j,s[col[j]]++;r[l[x]]=l[r[x]]=x;return; } bool dance(int dep){if(r[0]==0){for(int i=0;i<dep;i++)printf("%d ",ans[i]);return 1;}int c=r[0];for(int i=c;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[dep]=row[i];for(int j=r[i];j!=i;j=r[j])remove(col[j]);if(dance(dep+1))return 1;for(int j=l[i];j!=i;j=l[j])recover(col[j]);}recover(c);return 0; } int main() {scanf("%d%d",&n,&m);init();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x;scanf("%d",&x);if(x)link(i,j);}if(!dance(0))puts("No Solution!");return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4929-[模板]舞蹈链(DLX)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。