给出一个\(n\times m\)的01矩阵，每行最多有\(c\)个1，求一个精确覆盖，即选出一些行使得每列有有且仅有一个1。输出方案。
被这个题坑到了啊！！第一次上HUSTOJ做题，不知道没有ONLINE_JUDGE编译参数，又WA了几个小时。
我感觉这个spj是有问题的，只处理了顺序不同的问题，而没有处理方案不同，所以其实有些对的代码过不了。
我最开始看完这篇写的超级棒，主要是配了图的教程，然后自己乱写一个，发现很好写，才45行左右，然后就WA了。最终知道了是ONLINE_JUDGE的问题，但是，把之前的代码去掉文件读写还是会错！
WA的过程中，我去网上搜了很多题解。我要批判一下那些人啊，全都拿别人的代码来当模版……哎。
我在他们的代码中发现了一个优化。原来的教程中说的是找到Head右边的第一个开始搜索。其实搜索的顺序是无关的，因为这是基于所有的列都会被覆盖到，所以顺序无关。所以我们可以找其中列标下面剩余1的个数最少的那一列来找，可以大大剪枝。所以每一列维护一下size即可。
还有一个要注意的地方，我们在删除列和回退的时候，方向是不一样的。比如说，删除列我们一开始向下走走一圈，那么回退的时候我们向上走，估计是为了避免一些冲突。同样在便利我们要删除的行的时候，从左到右，回退从右到左。
网上那些“模版”写得那么奇怪还一堆人拿来抄。这个多漂亮～
#include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1e3+10; const int maxc=1e2+10; const int maxp=maxn*maxc; int a[maxc],ans[maxn]; struct node { int l,r,u,d,col,row; }; struct DLX { node p[maxp]; int tot,last[maxn],size[maxn]; void clear(int m) { tot=m; memset(last,0,sizeof last); memset(size,0,sizeof size); memset(p,0,sizeof p); p[0]=(node){0,0,0,0,0,0}; for (int i=1;i<=m;++i) { last[i]=i; p[i]=(node){i-1,p[i-1].r,i,i,i,0}; p[p[i].l].r=i,p[p[i].r].l=i; } } void build(int row,int a[],int len) { p[++tot]=(node){tot,tot,last[a[1]],p[last[a[1]]].d,a[1],row}; p[p[tot].u].d=p[p[tot].d].u=last[a[1]]=tot; ++size[p[tot].col]; for (int i=2;i<=len;++i) { int x=a[i]; p[++tot]=(node){tot-1,p[tot-1].r,last[x],p[last[x]].d,x,row}; p[p[tot].l].r=p[p[tot].r].l=p[p[tot].u].d=p[p[tot].d].u=last[x]=tot; ++size[p[tot].col]; } } void del(int c) { p[p[c].l].r=p[c].r,p[p[c].r].l=p[c].l; for (int i=p[c].d;i!=c;i=p[i].d) for (int j=p[i].r;j!=i;j=p[j].r) p[p[j].u].d=p[j].d,p[p[j].d].u=p[j].u,--size[p[j].col]; } void back(int c) { p[p[c].l].r=p[p[c].r].l=c; for (int i=p[c].u;i!=c;i=p[i].u) for (int j=p[i].r;j!=i;j=p[j].r) p[p[j].u].d=p[p[j].d].u=j,++size[p[j].col]; } int dance(int k) { if (p[0].r==0) return k; int first,mi=maxp; for (int i=p[0].r;i;i=p[i].r) if (size[i]<mi) mi=size[i],first=i; //here if (p[first].d==first) return 0; del(first); for (int i=p[first].d;i!=first;i=p[i].d) { for (int j=p[i].r;j!=i;j=p[j].r) del(p[j].col); ans[k+1]=p[i].row; int ret=dance(k+1); if (ret) return ret; ans[k+1]=0; for (int j=p[i].l;j!=i;j=p[j].l) back(p[j].col); } back(first); return 0; } } dlx; int main() { int n,m; while (~scanf("%d%d",&n,&m)) { dlx.clear(m); for (int i=1;i<=n;++i) { int c=read(); if (!c) continue; for (int j=1;j<=c;++j) a[j]=read(); sort(a+1,a+c+1); dlx.build(i,a,c); } int gs=dlx.dance(0); if (!gs) { puts("NO"); continue; } printf("%d ",gs); sort(ans+1,ans+gs+1); for (int i=1;i<=gs;++i) printf("%d ",ans[i]); puts(""); } return 0; }转载于:https://www.cnblogs.com/owenyu/p/6724554.html
相关资源：25个经典网站源代码