[Ural 1519 Formula 1]基于连通性的状态压缩动态规划

【题目大意】

给定一个M*N的矩阵，让你求其中非障碍格的哈密顿回路有多少种。

【算法分析】

按照CDQ的论文所写。

我用两个二进制位来表示插头：

00表示无插头

01表示“(”插头

10表示“)”插头

然后就分类讨论即可。

实现上，我用一个hash表来达到定位的目的。

因为这样表示状态很多，但是实际上状态是非常稀疏的，所以我开一个线性表来保存扩展到的状态，然后更新的时候，就从hash表里指向过去，然后维护一下就好了。

【其它】1A，跑了109MS

【CODE】

#include #include #include #include #define cf(x) (1<<(x))
using namespace std;
const int key=10003;
const int INF=0x7FFFFFFF;
typedef long long LL;
struct gtp{int y,next;}g[1000000];
int m,n,ng,pg,e,mx,my;
char c[13][13];
LL fl[2][20000],ans;
int sl[2][20000];
int tot[2],ls[key];

inline void init(){e=0;memset(ls,0,sizeof(ls));}
inline void addedge(int x,int y){e++; g[e].y=y; g[e].next=ls[x]; ls[x]=e;}
inline int ChaTou(int t1,int t2){
    if (!t1 && !t2) return 0;
    if (t1) return 1;
    return 2;
}   

void add(int s,LL f){
    int st=s%key;
    for (int t=ls[st];t;t=g[t].next)
      if (sl[ng][g[t].y]==s){
          fl[ng][g[t].y]+=f;
          return;
      }
    sl[ng][++tot[ng]]=s;
    fl[ng][tot[ng]]=f;
    addedge(st,tot[ng]);
}   

void input(){
    ng=1; pg=0; ans=0;
    scanf("%d%d",&m,&n);
    int i,j;
    for (i=0;i      for (j=0;j        for (c[i][j]=getchar();c[i][j]!=’*’&&c[i][j]!=’.’;c[i][j]=getchar());
    if (c[0][0]==’*’) add(0,1);
                 else add(1+cf(n*2+1),1);
    mx=0; my=0;
    for (i=0;i      for (j=0;j        if (c[i][j]==’.’){
            mx=i;
            my=j;
        }   
}   

void No(int j){
    int k,t1,t2;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        if ((s&cf(j*2))||(s&cf(j*2+1))||(cf(n*2)&s)||(cf(n*2+1)&s)) continue;
        add(s,fl[pg][k]);
    }   
}

void Yes(int I,int j){
    int k,lct,uct,ts,i,top,ct;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        LL &f=fl[pg][k];
        uct=ChaTou(s&cf(j*2),s&cf(j*2+1));
        lct=ChaTou(s&cf(n*2),s&cf(n*2+1));
        if (!j && lct) continue;
        ts=(INF-cf(j*2)-cf(j*2+1)-cf(n*2)-cf(n*2+1))&s;
        switch (lct){
            case 0:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2)|cf(n*2+1),f);
                        break;
                    case 1:
                        add(ts|cf(j*2),f);
                        add(ts|cf(n*2),f);
                        break;
                    case 2:
                        add(ts|cf(j*2+1),f);
                        add(ts|cf(n*2+1),f);
                        break;
                }   
                break;
            case 1:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2),f);
                        add(ts|cf(n*2),f);
                        break;
                    case 1:
                        top=0;
                        for (i=j;;i++){
                            ct=ChaTou(s&cf(i*2),s&cf(i*2+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }
                        add((ts^cf(i*2+1))|cf(i*2),f);
                        break;
                    case 2:
                        if (I==mx && j==my && ts==0) ans+=f;
                        break;
                }   
                break;
            case 2:
                switch (uct){
                    case 0:
                        add(ts|cf(j*2+1),f);
                        add(ts|cf(n*2+1),f);
                        break;
                    case 1:
                        add(ts,f);
                        break;
                    case 2:
                        top=0;
                        for (i=j;;i–){
                            ct=ChaTou(s&cf(i*2),s&cf(i*2+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }   
                        add((ts^cf(i*2))|cf(i*2+1),f);
                        break;
                }   
                break;
        }   
    }   
}            

void dp(){
    for (int i=0;i      for (int j=0;j          if (!i && !j) continue;
          ng=1-ng;
          pg=1-pg;
          tot[ng]=0;
          init();
          if (c[i][j]==’*’) No(j);
                       else Yes(i,j);
      }
}   

int main(){
    input();
    dp();
    cout << ans << endl;
    return 0;   
}