DancingLinks[HUST_1017]

因为输出少了个\n WA了半天。 而且以下两种写法效率不一样。  有待研究
DancingLinks用于优化搜索，核心在于resume操作，可以快速恢复被删除的结点
1. 1468ms
[cpp]  
/*http://acm.hust.edu.cn/problem.php?id=1017*/  
/*DLX*/  
#include<iostream>  
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
using namespace std;  
const int MAXN = 200000;  
const int MAXM = 1111;  
struct DLX{  
    int L[MAXN],R[MAXN],U[MAXN],D[MAXN],C[MAXN],Col[MAXN],Row[MAXN];  
    int S[MAXM],Ans[MAXM];  
    int tot,len;  
    void build(int N,int M){  
        memset(S,0,MAXM*sizeof(int));  
        //construct the head and col head  
        for(int i=0;i<=M;i++){  
            U[i] = D[i] = i;  
            L[i] = i-1;  
            R[i] = i+1;  
            C[i] = i;  
        }  
        L[0] = M, R[M] = 0; tot = M;  
        for(int i=1;i<=N;i++){  
            int K,T; scanf("%d",&K);  
            for(int j=1;j<=K;j++){  
                scanf("%d",&T);  
                int node = ++tot;  
                C[node] = Col[node] = T;  
                Row[node] = i;  
                S[T]++;//维护列链表节点数  
                //维护UD两个指针  
                D[node] = D[C[T]];  
                D[C[T]] = node;  
                U[D[node]] = node;  
                U[D[C[T]]] = C[T];  
                C[T] = node; //更新到尾  
                //维护LR两个指针  
                if(j==1) L[node] = node+K-1;  
                else L[node] = node-1;  
                if(j==K) R[node] = node-K+1;  
                else R[node] = node+1;  
            }  
        }  
        for(int i=1;i<=M;i++){  
            C[i] = i;  
        }//还原列头指针  
    }  
    void debug(){  
        for(int i=R[0];i!=0;i=R[i]){  
            printf("C%d: ",i); int r = 1;  
            for(int j=D[i];j!=i;j=D[j]){  
                int ri = Row[j]; //cout<<"ri "<<ri<<" "<<r<<endl;  
                while(ri>r){  
                    r++; printf("0 ");  
                }  
                printf("1 "); r++;  
                //printf("j: %d\n",j);  
                //system("pause");  
            }  
            printf("\n");  
        }  
    }  
    void remove(const int &c){  
        L[R[c]] = L[c];  
        R[L[c]] = R[c];  
        for(int i=D[c];i!=c;i=D[i]){  
            for(int j=R[i];j!=i;j=R[j]){  
                U[D[j]] = U[j];  
                D[U[j]] = D[j];  
                S[C[j]]--;  
            }  
        }  
    }  
    void resume(const int &c){  
        L[R[c]] = c;  
        R[L[c]] = c;  
        for(int i=D[c];i!=c;i=D[i]){  
            for(int j=R[i];j!=i;j=R[j]){  
                U[D[j]] = j;  
                D[U[j]] = j;  
                S[C[j]]++;  
            }  
        }  
    }  
    bool dfs(const int &k){  
        if(R[0]==0){  
            len = k;  
            return true;  
        }  
        int s(0x7fffffff),c;  
        for(int i=R[0];i!=0;i=R[i]){  
            if(S[i]<s){  
                c = i;  
                s = S[i];  
            }  
        }  
        remove(c);  
        for(int i=D[c];i!=c;i=D[i]){  
            Ans[k] = Row[i];  
            for(int j=R[i];j!=i;j=R[j]){  
                remove(C[j]);  
            }  
            if(dfs(k+1)){  
                return true;  
            }  
            for(int j=R[i];j!

补充：软件开发 , C++ ,