因為輸出少了個\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!=i;j=R[j]){ resume(C[j]); } } resume(c); return false; } void solve(){ if(dfs(0)){ printf("%d",len); for(int i=0;i<len;i++){ printf(" %d",Ans[i]); } puts(""); }else{ puts("NO"); } } }dlx; int main(){ int N,M; while(~scanf("%d%d",&N,&M)){ dlx.build(N,M); dlx.solve(); } return 0; } 2.328ms [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 = 2000000; 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){ for(int i=U[c];i!=c;i=U[i]){ for(int j=L[i];j!=i;j=L[j]){ U[D[j]] = j; D[U[j]] = j; S[C[j]]++; } } L[R[c]] = c; R[L[c]] = c; } 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=L[i];j!=i;j=L[j]){ resume(C[j]); } } resume(c); return false; } void solve(){ if(dfs(0)){ printf("%d",len); for(int i=0;i<len;i++){ printf(" %d",Ans[i]); } puts(""); }else{ puts("NO"); } } }dlx; int main(){ int N,M; www.2cto.com while(scanf("%d%d",&N,&M)!=EOF){ dlx.build(N,M); dlx.solve(); } return 0; }
