洛谷P1074 靶形数独（跳舞链）

传送门

坑着，等联赛之后再填（联赛挂了就不填了233）

 //minamoto
 #include<iostream>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 char buf[<<],*p1=buf,*p2=buf;
 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}
 inline int read(){
     #define num ch-'0'
     char ch;bool flag=;int res;
     while(!isdigit(ch=getc()))
     (ch=='-')&&(flag=true);
     for(res=num;isdigit(ch=getc());res=res*+num);
     (flag)&&(res=-res);
     #undef num
     return res;
 }
 int score[]={,,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,,                 ,,,,,,,,};
 const int N=,mm=N*N*N*N*N*+N,mn=N*N*N+N;
 int mp[][];
 int ans=-,sz;
 int U[mm],D[mm],L[mm],R[mm],C[mm],X[mm];
 int S[mn],Q[mn],H[mn];bool v[mn];
 void init(int r,int c){
     //建好虚拟节点
     for(int i=;i<=c;++i){
         S[i]=,U[i]=D[i]=i,
         L[i+]=i,R[i]=i+;
     }
     R[sz=c]=,L[]=sz;
     while(r) H[r--]=-;//判断每列是否有节点
 }
 void place(int &r,int &c1,int &c2,int &c3,int &c4,int i,int j,int k){
     //看不懂
     r=((i-)*N+j-)*N+k;
     c1=(i-)*N+j;
     c2=N*N+(i-)*N+k;
     c3=N*N*+(j-)*N+k;
     c4=N*N*+(((i-)/)*+(j-)/)*N+k;
 }
 void link(int r,int c){
     //S记录每列的元素个数，C是个队列，记录总的节点个数（大概）
     //好像看不太懂这跳舞链怎么连的……
     ++S[C[++sz]=c];
     X[sz]=r,D[sz]=D[c],U[D[c]]=sz,
     U[sz]=c,D[c]=sz;
     if(H[r]==-) H[r]=L[sz]=R[sz]=sz;//这行没有的话就都先连起来
     else{
         R[sz]=R[H[r]],L[R[H[r]]]=sz,
         L[sz]=H[r],R[H[r]]=sz;
     }
 }
 void remove(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])
     D[U[j]]=D[j],U[D[j]]=U[j],--S[C[j]];
 }
 void resume(int c){
     for(int i=U[c];i!=c;i=U[i])
     for(int j=L[i];j!=i;j=L[j])
     ++S[C[D[U[j]]=U[D[j]]=j]];
     L[R[c]]=R[L[c]]=c;
 }
 void dance(int k){
     if(!R[]){
         int res=;
         for(int i=;i<k;++i)
         res+=score[(X[Q[i]]-)/N+]*((X[Q[i]]-)%N+);
         cmax(ans,res);
         return;
     }
     int tmp=mm,c;
     for(int i=R[];i;i=R[i])
     if(S[i]<tmp) tmp=S[c=i];
     remove(c);
     for(int i=D[c];i!=c;i=D[i]){
         Q[k]=i;
         for(int j=R[i];j!=i;j=R[j]) remove(C[j]);
         dance(k+);
         for(int j=L[i];j!=i;j=L[j]) resume(C[j]);
     }
     resume(c);
 }
 int main(){
 //    freopen("testdata.in","r",stdin);
     int r,c1,c2,c3,c4;
     init(mn,N*N*);
     for(int i=;i<=N;++i)
     for(int j=;j<=N;++j){
         mp[i][j]=read();
         if(mp[i][j]){
             place(r,c1,c2,c3,c4,i,j,mp[i][j]);
             link(r,c1),link(r,c2),link(r,c3),link(r,c4);
             v[c1]=v[c2]=v[c3]=v[c4]=;
         }
     }
     for(int i=;i<=N;++i)
     for(int j=;j<=N;++j)
     for(int k=;k<=N;++k){
         place(r,c1,c2,c3,c4,i,j,k);
         if(v[c1]||v[c2]||v[c3]||v[c4])continue;
         link(r,c1),link(r,c2),link(r,c3),link(r,c4);
     }
     dance();
     printf("%d\n",ans);
     return ;
 }