题解 P3342 【[ZJOI2014]璀灿光华】

· · 题解

6^8*70爆搜是容易的，

难度在于如何利用每个点相邻的点的编号得到每个点的坐标。

用(x,y,z)表示在平面上坐标(x,y)，高度z的点。

首先，我们找一个度数为3的点，把他当成(1,1,1)。

假如得到高度为1的那一层平面，我们就可以一层层推上去。

考虑如何从当前1-a,1-a这样的一个正方形扩展成a+1的。

高度为1的点的特点是度数=4(如果在边缘上)或5，而上面的点的度数是5或6。

所以我们可以先用原来度数=4的两个点找出现在度数=4的两个点，

之后从他们开始bfs,只有当一个点有两个已访问的相邻点时才访问它。

还有一点，就是读入时你不知道要读几个，必须读到换行为止，

于是我直接用了读入优化。

#include<bits/stdc++.h>
using std::swap;

const int A=75,N=A*A*A+5;
int a,n,x,y;
int mn=1e9,mx=0;
int g[N],du[N],link[N][7];
struct point
{
    int x,y,z;
}p[N];
int have[N];//有多少个已访问的相邻点 

namespace kcz
{
    const int ch_top=10000000;
    char ch[ch_top],*p=ch;
    void read(int &x)
    {
        while(*p<'0') ++p;
        for(x=*p-'0';*++p>='0';) x=(x<<1)+(x<<3)+*p-'0';
    }
    void init()
    {
        ch[fread(ch,1,ch_top,stdin)]='\n';
    }
    void init(int x)
    {
        read(g[x]);
        int &i=du[x];
        for(;;++i)
        {
            for(;*p<'0';++p)  
            if(*p=='\n') return ;
            read(link[x][i]);
        }
    }
};

int q[N],head,tail;

void Add(int x)
{
    for(int i=0,y;i<du[x];++i) 
    if(++have[y=link[x][i]]==2&&!p[y].x) q[++tail]=y;
}
void get(int x)
{
    int p1=0,p2,i;
    for(i=0,y;i<du[x];++i) 
    if(p[y=link[x][i]].x) 
     if(!p1)p1=y;
     else {p2=y;break;}
    if(p[p1].x>p[p2].x) swap(p1,p2);
    p[x]=(point){p[p2].x,p[p1].y,1};
}

const int fx[6]={0,0,0,0,1,-1},fy[6]={0,0,1,-1,0,0},fz[6]={1,-1,0,0,0,0};
int dy[A][A][A],mark[N],to;
bool ok(int x)
{
    return x>0&&x<=a;
}
void dfs(int num,int ans)
{
    if(num>tail) 
    {
      if(ans<mn)mn=ans;
      if(ans>mx)mx=ans;    
      return;
    }
    int k=q[num];
    for(int i=0;i<6;++i)
    {
        int x=p[k].x,y=p[k].y,z=p[k].z,sum=0;
        while(to=dy[x][y][z])
        {
            if(++mark[to]==1) sum+=g[to]; 
            x+=fx[i];y+=fy[i];z+=fz[i];
        }
        dfs(num+1,ans+sum);
        x=p[k].x;y=p[k].y;z=p[k].z;
        while(to=dy[x][y][z])
        {
           --mark[to];
            x+=fx[i];y+=fy[i];z+=fz[i];
        }
    }
}

int main()
{
    freopen("1.in","r",stdin);
    kcz::init();
    kcz::read(a);n=a*a*a;
    int i;
    for(i=1;i<=n;++i) 
     kcz::init(i);

    for(i=1;du[i]!=3;++i);
    p[i]=(point){1,1,1};Add(q[tail=1]=i);
    p[q[++tail]=link[i][0]]=(point){1,2,1};
    p[q[++tail]=link[i][1]]=(point){2,1,1};
    Add(q[2]);Add(q[3]);
    p[q[4]]=(point){2,2,1};
    Add(q[4]);

    int len=2,need,t0;
    for(head=2;len<a;++len)
    {
        if(len==a-1) need=3;
        else need=4;
          x=q[head];
          for(int i=0,y;i<du[x];++i) 
          if(du[y=link[x][i]]==need&&!p[y].x) 
          {
               p[y]=(point){1,len+1,1};
               q[++tail]=y;
               break;
          }
          x=q[head+1];
          for(int i=0,y;i<du[x];++i) 
          if(du[y=link[x][i]]==need&&!p[y].x) 
          {
               p[y]=(point){len+1,1,1};
               q[++tail]=y;
               break;
          }
        head=tail-1;
        for(int k=head;;++k)
        {
            x=q[k];
            Add(x);
            if(k==tail) break;
            get(q[tail]);
        }
    }

    for(head=1;head<=tail;)
    {
        t0=tail;
        for(;head<=t0;++head) 
        {
            x=q[head];
            for(i=0;y=link[x][i];++i)
            if(!p[y].x) 
            {
                q[++tail]=y;
                p[y]=(point){p[x].x,p[x].y,p[x].z+1};
                break;
            }
        }
    }

    tail=0;
    for(i=1;i<=n;++i)
    {
      dy[p[i].x][p[i].y][p[i].z]=i;
      if(!g[i]) q[++tail]=i;
    }
    dfs(1,0);
    printf("%d %d\n",mn,mx);
}