第一道DLX 的题， 算是模板题吧。
看了很久的论文才看懂， 双向十字链表第一次写还是有点纠结。 但是耐心点还是没有问题的。
搜素的优化，感觉这个超高效率的优化应该可以应用在很多方面。 在实现的过程中还有一个需要注意的东西，就是remove 和resume 要对称，不然就可能导致时间很慢或错误。。。
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define N 111000 #define INF 0x3fffffffint n,m; int g[1010][1010]; int u[N],d[N],r[N],l[N],c[N],line[N],ans[1010],num[1010]; int head; int tflag;/ int tg[1010][1010]; int why=0;void remove(int s) {why++;r[l[s]]=r[s];l[r[s]]=l[s];for(int i=d[s];i!=s;i=d[i]){for(int j=r[i];j!=i;j=r[j]){num[c[j]]--;u[d[j]]=u[j];d[u[j]]=d[j];}} }void resume(int s) {why++;r[l[s]]=s;l[r[s]]=s;for(int i=u[s];i!=s;i=u[i]){for(int j=l[i];j!=i;j=l[j]){num[c[j]]++;u[d[j]]=j;d[u[j]]=j;}} }void print() {memset(tg,0,sizeof(tg));for(int i=r[head];i!=head;i=r[i]){for(int j=d[i];j!=i;j=d[j]){tg[line[j]][c[j]]=1;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%d ",tg[i][j]);printf("\n");} }int dfs(int s) {if(tflag==1) return 1;if(r[head]==head){tflag=1;printf("%d ",s);for(int i=0;i<s;i++)printf("%d ",ans[i]);return 1;}int mi=INF;int u1;for(int i=r[head];i!=head;i=r[i]){if(num[i]< mi){mi=num[i];u1=i;}}remove(u1);//print();for(int i=d[u1];i!=u1;i=d[i]){ans[s] = line[i];for(int j=r[i];j!=i;j=r[j]){remove(c[j]);//print(); }if( dfs(s+1) == 1 ) return 1;for(int j=l[i];j!=i;j=l[j])resume(c[j]);}resume(u1); // 回复时与顺序无关...return 0; }int main() {while(scanf("%d%d",&n,&m)!=EOF){tflag=0;memset(ans,-1,sizeof(ans));memset(g,-1,sizeof(g));int id=1;head=0;r[0]=0; l[0]=0;int tmp=0;for(int i=1;i<=m;i++){c[id]=i;l[id]=tmp;r[id]=r[tmp];r[tmp]=id;l[head]=id;tmp=id;id++;}for(int i=1;i<=n;i++){int thead=-1;int cnt;scanf("%d",&cnt);tmp=-1;for(int j=0;j<cnt;j++){int pos;scanf("%d",&pos);g[i][pos]=id;line[id]=i;if(thead==-1){thead=id;tmp=id;l[tmp]=tmp;r[tmp]=tmp;}else{l[id]=tmp;r[id]=r[tmp];r[tmp]=id;l[thead]=id;tmp=id;}tmp=id;id++;}}///for(int j=1; j<=m ;j++){int tcnt=0;int thead=j;int tid;u[thead]=thead;d[thead]=thead;tmp=thead;for(int i=1 ; i<=n ; i++){if(g[i][j]!=-1){tcnt++;tid=g[i][j];u[tid]=tmp;d[tid]=d[tmp];d[tmp]=tid;u[thead]=tid;tmp=tid;c[tid]=j;}}num[j]=tcnt; // 这一列有多少元素... }/int flag = dfs(0);if(flag==0) printf("NO\n");else{printf("\n");}printf("why=%d\n",why);}return 0; }