给出一个(n imes 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;
}