zoj 3213 Beautiful Meadow

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3213

题目大意：求最大简单回路。

题目思路：插头dp,增加独立插头，有可不走点需要特殊处理一下。这个题写得相当纠结啊，写括号表示法的时候有一个地方忘了处理了，花了一晚上都没调出来，今早上用最小表示法打数据对比才找到了错误，真是相当辛苦啊，不过括号表示法的效率依然不错，跑了80ms。

最小表示法：

#include<stdio.h>
#include<string.h>
#define Max 20000
#define Hash 3007
#define  __int64 long long
int code[15],ch[15],mp[15][15],ex,ey,n,m,cur,ans,num;
char str[15];
inline int max(int a,int b)
{
    return a>b?a:b;
}
struct node
{
    int size,next[Max],p[Hash],f[Max];
    __int64 state[Max];
    inline void init()
    {
        memset(p,-1,sizeof(p));
        size=0;
    }
    inline void push(__int64 st,int val)
    {
        int i,u=st%Hash;
        for(i=p[u];i!=-1;i=next[i])
        {
            if(state[i]==st)
            {
                if(val>f[i]) f[i]=val;
                return;
            }
        }
        state[size]=st;f[size]=val;
        next[size]=p[u];
        p[u]=size++;
    }
}dp[2];
inline void decode(__int64 st)
{
    memset(ch,0,sizeof(ch));
   num=st&7;
   st>>=3;
    for(int i=m;i>=0;i--)
    {
        code[i]=st&7;
        st>>=3;
    }
}
inline __int64 encode()
{
    __int64 st=0;
    int cnt=1;
    memset(ch,-1,sizeof(ch));
    ch[0]=0;
    for(int i=0;i<=m;i++)
    {
        if(ch[code[i]]==-1)
            ch[code[i]]=cnt++;
        st<<=3;
        st|=ch[code[i]];
    }
    st<<=3;
    st|=num;
    return st;
}
inline void shift()
{
    for(int k=0;k<dp[cur].size;k++)
    {
        num=dp[cur].state[k]&7;
        dp[cur^1].push((dp[cur].state[k]>>3)|num,dp[cur].f[k]);
    }
}
inline void dpblank(int i,int j)
{
    int k,l,left,up;
    for(k=0;k<dp[cur].size;k++)
    {
        int tmp=dp[cur].f[k]+mp[i][j];
        decode(dp[cur].state[k]);
        left=code[j-1],up=code[j];
        if(left&&up)
        {
            if(left!=up)
            {
                code[j-1]=code[j]=0;
                for(l=0;l<=m;l++)
                    if(code[l]==up)
                        code[l]=left;
                dp[cur^1].push(encode(),tmp);
            }
        }
        else if(left||up)
        {

            if(mp[i][j+1])
            {
                code[j-1]=0;code[j]=left+up;
                dp[cur^1].push(encode(),tmp);
            }
            if(mp[i+1][j])
            {
                code[j-1]=left+up,code[j]=0;
                dp[cur^1].push(encode(),tmp);
            }
            if(num<2)
            {
                num++;
                code[j-1]=code[j]=0;
                dp[cur^1].push(encode(),tmp);
            }
        }
        else
        {
            code[j-1]=code[j]=0;
            dp[cur^1].push(encode(),dp[cur].f[k]);
            if(mp[i][j+1]&&mp[i+1][j])
            {
                code[j-1]=code[j]=7;
                dp[cur^1].push(encode(),tmp);
            }
            if(num<2)
            {
                num++;
                if(mp[i][j+1])
                {
                    code[j-1]=0,code[j]=7;
                    dp[cur^1].push(encode(),tmp);
                }
                if(mp[i+1][j])
                {
                    code[j-1]=7,code[j]=0;
                    dp[cur^1].push(encode(),tmp);
                }
            }
        }
    }
}
void solve()
{
    int i,j,k;
    cur=0;
    dp[0].init();
    dp[0].push(0,0);
    for(i=1;i<=n;i++)
    {
        dp[cur^1].init();
        shift();
        cur^=1;
        for(j=1;j<=m;j++)
        {
            if(mp[i][j])
            {
                dp[cur^1].init();
                dpblank(i,j);
                cur^=1;
            }
        }
    }
    for(k=0;k<dp[cur].size;k++)
        if(ans<dp[cur].f[k])
            ans=dp[cur].f[k];
    printf("%d\n",ans);
}
int main()
{
    int i,j,t;
  //  freopen("D:/out.txt","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        ex=0;
        memset(mp,0,sizeof(mp));
        for(i=1;i<=n;i++)
           for(j=1;j<=m;j++)
           {
                scanf("%d",&mp[i][j]);
                ans=max(ans,mp[i][j]);
           }
        solve();
    }
    return 0;
}

括号表示法：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 20010
#define Hash 3007
int n,m,ex,ey,cur,mp[15][15],a1,a2,a3,b1,b2,b3,ans,num;
int stack[15],f[15];
char str[15];
struct node
{
    int size,next[Max],p[Hash],state[Max];
    int f[Max];
    inline void init()
    {
        memset(p,-1,sizeof(p));
        size=0;
    }
    inline void push(int st,int val)
    {
        int i,u=st%Hash;
        for(i=p[u];i!=-1;i=next[i])
        {
            if(state[i]==st)
            {
                if(f[i]<val) f[i]=val;
                return;
            }
        }
        state[size]=st;f[size]=val;
        next[size]=p[u];
        p[u]=size++;
    }
}dp[2];
inline void decode(int st)
{
    int top=0;
    st>>=2;
    for(int i=0;i<=m;i++)
    {
        if((st&3)==1)
            stack[top++]=i;
        else if((st&3)==2)
        {
            f[stack[top-1]]=i+1;
            f[i]=stack[top-1]+1;
            top--;
        }
        st>>=2;
    }
}
inline void shift()
{
    for(int k=0;k<dp[cur].size;k++)
    {
        num=dp[cur].state[k]&3;
        dp[cur].state[k]^=num;
        dp[cur^1].push((dp[cur].state[k]<<2)|num,dp[cur].f[k]);
    }
}
inline void dpblank(int i,int j)
{
    int k,left,up;
    for(k=0;k<dp[cur].size;k++)
    {
       	int st=dp[cur].state[k];
        int tmp=dp[cur].f[k]+mp[i][j];
        left=st&a3;up=st&b3;num=st&3;
        if(left&&up)
        {
            decode(st);
            if(left==a2&&up==b1)
                dp[cur^1].push(st^left^up,tmp);
            else if(left==a1&&up==b1)
                dp[cur^1].push(st^left^up^(3<<(2*f[j])),tmp);
            else if(left==a2&&up==b2)
                dp[cur^1].push(st^left^up^(3<<(2*f[j-1])),tmp);
            else if(left==a3&&up==b3)
                dp[cur^1].push(st^left^up,tmp);
            else if(left==a3)
                dp[cur^1].push((st^left^up)|(3<<(2*f[j])),tmp);
            else if(up==b3)
                dp[cur^1].push((st^left^up)|(3<<(2*f[j-1])),tmp);
        }
        else if(left)
        {
            if(mp[i][j+1])
                dp[cur^1].push((st^left)|(left<<2),tmp);
            if(mp[i+1][j])
                dp[cur^1].push(st,tmp);
            if(num<2)
            {
                num++;decode(st);
				int ss=(st^left^up)|num;
				if(left!=a3)
					ss|=3<<(2*f[j-1]);
                dp[cur^1].push(ss,tmp);
            }
        }
        else if(up)
        {
            if(mp[i][j+1])
                dp[cur^1].push(st,tmp);
            if(mp[i+1][j])
                dp[cur^1].push((st^up)|(up>>2),tmp);
            if(num<2)
            {
                num++;decode(st);
				int ss=(st^left^up)|num;
				if(up!=b3)
					ss|=3<<(2*f[j]);
                dp[cur^1].push(ss,tmp);
            }
        }
        else
        {
            dp[cur^1].push(st^left^up,dp[cur].f[k]);
            if(mp[i][j+1]&&mp[i+1][j])
                dp[cur^1].push(st|a1|b2,tmp);
            if(num<2)
            {
                num++;
                if(mp[i][j+1])
                dp[cur^1].push((st|b3)|num,tmp);
                if(mp[i+1][j])
                dp[cur^1].push((st|a3)|num,tmp);
            }
        }
    }
}
inline void solve()
{
    int i,j,k;
    cur=0;
    dp[0].init();
    dp[0].push(0,0);
    for(i=1;i<=n;i++)
    {
        dp[cur^1].init();
        shift();
        cur^=1;
        b1=4;b2=8;
        for(j=1;j<=m;j++)
        {
            a1=b1;a2=b2;a3=a1|a2;
            b1<<=2;b2<<=2;b3=b1|b2;
            if(mp[i][j])
            {
                dp[cur^1].init();
                dpblank(i,j);
                cur^=1;
            }
        }
    }
     for(k=0;k<dp[cur].size;k++)
        if(ans<dp[cur].f[k])
            ans=dp[cur].f[k];
    printf("%d\n",ans);
}
int main()
{
    int i,j,t;
   //freopen("D:/out2.txt","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        memset(mp,0,sizeof(mp));
        for(i=1;i<=n;i++)
           for(j=1;j<=m;j++)
           {
                scanf("%d",&mp[i][j]);
                if(ans<mp[i][j]) ans=mp[i][j];
           }
        solve();
    }
    return 0;
}

括号表示法的另一种写法（不加独立插头个数限制）：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 20010
#define Hash 3007
int n,m,ex,ey,cur,mp[15][15],a1,a2,a3,b1,b2,b3,ans;
int stack[15],f[15];
char str[15];
struct node
{
    int size,next[Max],p[Hash],state[Max];
    int f[Max];
    inline void init()
    {
        memset(p,-1,sizeof(p));
        size=0;
    }
    inline void push(int st,int val)
    {
        int i,u=st%Hash;
        for(i=p[u];i!=-1;i=next[i])
        {
            if(state[i]==st)
            {
                if(f[i]<val) f[i]=val;
                return;
            }
        }
        state[size]=st;f[size]=val;
        next[size]=p[u];
        p[u]=size++;
    }
}dp[2];
inline void decode(int st)
{
    int top=0;
    for(int i=0;i<=m;i++)
    {
        if((st&3)==1)
            stack[top++]=i;
        else if((st&3)==2)
        {
            f[stack[top-1]]=i;
            f[i]=stack[top-1];
            top--;
        }
        st>>=2;
    }
}
inline void shift()
{
    for(int k=0;k<dp[cur].size;k++)
        dp[cur^1].push((dp[cur].state[k]<<2),dp[cur].f[k]);
}
inline void dpblank(int i,int j)
{
    int k,left,up;
    for(k=0;k<dp[cur].size;k++)
    {
       	int st=dp[cur].state[k];
        int tmp=dp[cur].f[k]+mp[i][j];
        left=st&a3;up=st&b3;
        if(left&&up)
        {
            decode(st);
            if(left==a2&&up==b1)
                dp[cur^1].push(st^left^up,tmp);
            else if(left==a1&&up==b1)
                dp[cur^1].push(st^left^up^(3<<(2*f[j])),tmp);
            else if(left==a2&&up==b2)
                dp[cur^1].push(st^left^up^(3<<(2*f[j-1])),tmp);
            else if(left==a3&&up==b3)
            {
                if((st^left^up)==0&&ans<tmp) ans=tmp;
            }
            else if(left==a3)
                dp[cur^1].push((st^left^up)|(3<<(2*f[j])),tmp);
            else if(up==b3)
                dp[cur^1].push((st^left^up)|(3<<(2*f[j-1])),tmp);
        }
        else if(left)
        {
            if(mp[i][j+1])
                dp[cur^1].push((st^left)|(left<<2),tmp);
            if(mp[i+1][j])
                dp[cur^1].push(st,tmp);
            if(left!=a3)
            {
                decode(st);
                dp[cur^1].push((st^left^up)|(3<<(2*f[j-1])),tmp);
            }
            if(left==a3)
            {
                if((st^left^up)==0&&ans<tmp) ans=tmp;
            }

        }
        else if(up)
        {
            if(mp[i][j+1])
                dp[cur^1].push(st,tmp);
            if(mp[i+1][j])
                dp[cur^1].push((st^up)|(up>>2),tmp);
            if(up!=b3)
            {
                decode(st);
                dp[cur^1].push((st^left^up)|(3<<(2*f[j])),tmp);
            }
            if(up==b3)
            {
                if((st^left^up)==0&&ans<tmp) ans=tmp;
            }
        }
        else
        {
            dp[cur^1].push(st^left^up,dp[cur].f[k]);
            if(mp[i][j+1]&&mp[i+1][j])
                dp[cur^1].push(st|a1|b2,tmp);
            if(mp[i][j+1])
                dp[cur^1].push((st|b3),tmp);
            if(mp[i+1][j])
                dp[cur^1].push((st|a3),tmp);
        }
    }
}
inline void solve()
{
    int i,j;
    cur=0;
    dp[0].init();
    dp[0].push(0,0);
    for(i=1;i<=n;i++)
    {
        dp[cur^1].init();
        shift();
        cur^=1;
        b1=1;b2=2;
        for(j=1;j<=m;j++)
        {
            a1=b1;a2=b2;a3=a1|a2;
            b1<<=2;b2<<=2;b3=b1|b2;
            if(mp[i][j])
            {
                dp[cur^1].init();
                dpblank(i,j);
                cur^=1;
            }
        }
    }
    printf("%d\n",ans);
}
int main()
{
    int i,j,t;
   //freopen("D:/out2.txt","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        memset(mp,0,sizeof(mp));
        for(i=1;i<=n;i++)
           for(j=1;j<=m;j++)
           {
                scanf("%d",&mp[i][j]);
                if(ans<mp[i][j]) ans=mp[i][j];
           }
        solve();
    }
    return 0;
}