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

坑着，等联赛之后再填（联赛挂了就不填了233）
  1 //minamoto
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 using namespace std;
  6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
  7 char buf[1<<21],*p1=buf,*p2=buf;
  8 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
  9 inline int read(){
 10     #define num ch-'0'
 11     char ch;bool flag=0;int res;
 12     while(!isdigit(ch=getc()))
 13     (ch=='-')&&(flag=true);
 14     for(res=num;isdigit(ch=getc());res=res*10+num);
 15     (flag)&&(res=-res);
 16     #undef num
 17     return res;
 18 }
 19 int score[100]={0,6,6,6,6,6,6,6,6,6,
 20 
 21                 6,7,7,7,7,7,7,7,6,
 22                 
 23                 6,7,8,8,8,8,8,7,6,
 24                 
 25                 6,7,8,9,9,9,8,7,6,
 26                 
 27                 6,7,8,9,10,9,8,7,6,
 28                 
 29                 6,7,8,9,9,9,8,7,6,
 30                 
 31                 6,7,8,8,8,8,8,7,6,
 32                 
 33                 6,7,7,7,7,7,7,7,6,
 34 
 35                 6,6,6,6,6,6,6,6,6};
 36 const int N=9,mm=N*N*N*N*N*4+N,mn=N*N*N+N;
 37 int mp[10][10];
 38 int ans=-1,sz;
 39 int U[mm],D[mm],L[mm],R[mm],C[mm],X[mm];
 40 int S[mn],Q[mn],H[mn];bool v[mn];
 41 void init(int r,int c){
 42     //建好虚拟节点 
 43     for(int i=0;i<=c;++i){
 44         S[i]=0,U[i]=D[i]=i,
 45         L[i+1]=i,R[i]=i+1;
 46     }
 47     R[sz=c]=0,L[0]=sz;
 48     while(r) H[r--]=-1;//判断每列是否有节点 
 49 }
 50 void place(int &r,int &c1,int &c2,int &c3,int &c4,int i,int j,int k){
 51     //看不懂 
 52     r=((i-1)*N+j-1)*N+k;
 53     c1=(i-1)*N+j;
 54     c2=N*N+(i-1)*N+k;
 55     c3=N*N*2+(j-1)*N+k;
 56     c4=N*N*3+(((i-1)/3)*3+(j-1)/3)*N+k;
 57 }
 58 void link(int r,int c){
 59     //S记录每列的元素个数，C是个队列，记录总的节点个数（大概） 
 60     //好像看不太懂这跳舞链怎么连的…… 
 61     ++S[C[++sz]=c];
 62     X[sz]=r,D[sz]=D[c],U[D[c]]=sz,
 63     U[sz]=c,D[c]=sz;
 64     if(H[r]==-1) H[r]=L[sz]=R[sz]=sz;//这行没有的话就都先连起来 
 65     else{
 66         R[sz]=R[H[r]],L[R[H[r]]]=sz,
 67         L[sz]=H[r],R[H[r]]=sz;
 68     }
 69 }
 70 void remove(int c){
 71     L[R[c]]=L[c],R[L[c]]=R[c];
 72     for(int i=D[c];i!=c;i=D[i])
 73     for(int j=R[i];j!=i;j=R[j])
 74     D[U[j]]=D[j],U[D[j]]=U[j],--S[C[j]];
 75 }
 76 void resume(int c){
 77     for(int i=U[c];i!=c;i=U[i])
 78     for(int j=L[i];j!=i;j=L[j])
 79     ++S[C[D[U[j]]=U[D[j]]=j]];
 80     L[R[c]]=R[L[c]]=c;
 81 }
 82 void dance(int k){
 83     if(!R[0]){
 84         int res=0;
 85         for(int i=0;i<k;++i)
 86         res+=score[(X[Q[i]]-1)/N+1]*((X[Q[i]]-1)%N+1);
 87         cmax(ans,res);
 88         return;
 89     }
 90     int tmp=mm,c;
 91     for(int i=R[0];i;i=R[i])
 92     if(S[i]<tmp) tmp=S[c=i];
 93     remove(c);
 94     for(int i=D[c];i!=c;i=D[i]){
 95         Q[k]=i;
 96         for(int j=R[i];j!=i;j=R[j]) remove(C[j]);
 97         dance(k+1);
 98         for(int j=L[i];j!=i;j=L[j]) resume(C[j]);
 99     }
100     resume(c);
101 }
102 int main(){
103 //    freopen("testdata.in","r",stdin);
104     int r,c1,c2,c3,c4;
105     init(mn,N*N*4);
106     for(int i=1;i<=N;++i)
107     for(int j=1;j<=N;++j){
108         mp[i][j]=read();
109         if(mp[i][j]){
110             place(r,c1,c2,c3,c4,i,j,mp[i][j]);
111             link(r,c1),link(r,c2),link(r,c3),link(r,c4);
112             v[c1]=v[c2]=v[c3]=v[c4]=1;
113         }
114     }
115     for(int i=1;i<=N;++i)
116     for(int j=1;j<=N;++j)
117     for(int k=1;k<=N;++k){
118         place(r,c1,c2,c3,c4,i,j,k);
119         if(v[c1]||v[c2]||v[c3]||v[c4])continue;
120         link(r,c1),link(r,c2),link(r,c3),link(r,c4);
121     }
122     dance(0);
123     printf("%d
",ans);
124     return 0;
125 }