黄石网站设计公司,网页链接 提取码:qqcd,网站建设裕鸿国际,用钢铁侠做网站正题
题目链接:https://www.luogu.com.cn/problem/P4929 题目大意 n∗mn*mn∗m的矩形有0/10/10/1#xff0c;要求选出若干行使得每一列有且仅有一个111。 解题思路
精确覆盖问题指的是一个集合SSS和它的若干个子集集合TTT#xff0c;要求选出TTT的一个子集使得里面的集合元…正题
题目链接:https://www.luogu.com.cn/problem/P4929 题目大意
n∗mn*mn∗m的矩形有0/10/10/1要求选出若干行使得每一列有且仅有一个111。 解题思路
精确覆盖问题指的是一个集合SSS和它的若干个子集集合TTT要求选出TTT的一个子集使得里面的集合元素刚好覆盖集合SSS。 DLXDLXDLX全称是dancinglinkXdancing\ link\ Xdancing link X其中dancinglinkdancing\ linkdancing link是指交叉十字循环双向链XXX是指暴搜。
知道了这些就可以去看洛谷题解了 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N10100;
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 i0;im;i)l[i]i-1,r[i]i1,u[i]d[i]i;l[0]m;r[m]0;cntm;
}
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 id[x];i!x;id[i])for(int jr[i];j!i;jr[j])u[d[j]]u[j],d[u[j]]d[j],s[col[j]]--;return;
}
void recover(int x){for(int iu[x];i!x;iu[i])for(int jl[i];j!i;jl[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 i0;idep;i)printf(%d ,ans[i]);return 1;}int cr[0];for(int ic;i!0;ir[i])if(s[i]s[c])ci;remove(c);for(int id[c];i!c;id[i]){ans[dep]row[i];for(int jr[i];j!i;jr[j])remove(col[j]);if(dance(dep1))return 1;for(int jl[i];j!i;jl[j])recover(col[j]);}recover(c);return 0;
}
int main()
{scanf(%d%d,n,m);init();for(int i1;in;i)for(int j1;jm;j){int x;scanf(%d,x);if(x)link(i,j);}if(!dance(0))puts(No Solution!);return 0;
}
