tj

开荒、

#include <cstring>
#include <iostream>
#include <fstream>
#include <sstream>//stringstream
#include <queue>
  
using namespace std;
  
const int maxm = 2058000;//這裏的最大邊數我是把點數加起來乘了6
const int maxn = 75*75*75;
const int inf = 0x3f3f3f3f;
  
int n;//總個數
int tn;//邊長
  
struct Edge
{
    int to, nxt;
} e[maxm<<1];
  
int first[maxn];
  
int cnt;
inline void add_edge(int f, int t)
{
    e[++cnt].nxt = first[f];
    first[f] = cnt;
    e[cnt].to = t;
}
  
int dirx[] = {1, -1, 0, 0, 0, 0};
int diry[] = {0, 0, 1, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
  
int dep[maxn];//"好看程度"
int vis[maxn];
int minn = inf;
int maxx = -inf;
int ll[10];//會發光的水晶的編號
int ddn[maxn];//度數
int zl;//這是個ddn的cnt
int mmap[73][73][73];
  
struct zb
{
    int x, y, z;
} poi[maxn];
  
#define pan (x > 0 && x <= tn && y > 0 && y <= tn && z > 0 && z <= tn)
#define nxxt x += dirx[i], y += diry[i], z += dirz[i]
  
inline int getans(int i, zb a)//能加多少"好看程度"
{
    int ans = 0;
    int x = a.x, y = a.y, z = a.z;
    for(; pan; nxxt)
        if(!vis[mmap[x][y][z]]++)//由於待會兒回溯時要刪除，所以懶到家的我就直接用++,--代替記錄了
            ans += dep[mmap[x][y][z]];
    return ans;
}
  
inline void delvis(int i, zb a)//回溯時把dfs前加的vis刪除
{
    int x = a.x, y = a.y, z = a.z;
    for(; pan; nxxt)
        vis[mmap[x][y][z]]--;
}
  
inline void dfs(int now, int ans)//大力枚舉所有情況
{
    if(now > zl)
    {
        minn = min(minn, ans);
        maxx = max(maxx, ans);
        return;
    }
    for(int i = 0; i < 6; ++i)
    {
        dfs(now+1, ans + getans(i, poi[ll[now]]));
        delvis(i, poi[ll[now]]);
    }
}
  
int dist[4][maxn];
int di[4];
bool viss[maxn];
  
inline void bfs(int id)//求最短路
{
    memset(viss, 0, sizeof(viss));
    queue<int> q;
    int from = di[id];
    viss[from] = true;
    q.push(from);
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        for(int i = first[now]; i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(!viss[to])
            {
                viss[to] = true;
                dist[id][to] = dist[id][now] + 1;
                q.push(to);
            }
        }
    }
}
  
int main()
{
    ios:: sync_with_stdio(false);
    cin >> n;
    tn = n;
    string tmp;
    getline(cin, tmp);
    n *= n * n;
    for(int i = 1; i <= n; ++i)
    {
        getline(cin, tmp);
        stringstream ss(tmp);
        ss >> dep[i];
        int aa;
        if(!dep[i])
        {
            vis[i] = true;
            ll[++zl] = i;
        }
        while(ss >> aa)
        {
            add_edge(i, aa);
            ddn[i]++;
        }
    }
    for(di[0] = 1; ddn[di[0]] > 3; ++di[0]);
    bfs(0);
    for(int i = 1; i <= n; ++i)
    {
        if(ddn[i] == 3 && dist[0][i] == ((tn-1)<<1))
        {
            di[1] = i;
            break;
        }
    }
    bfs(1);
    for(int i = 1; i <= n; ++i)//得到z
    {
        poi[i].z = (dist[0][i] + dist[1][i] - ((tn-2)<<1)) >> 1;
        if(poi[i].z == tn && dist[0][i] == dist[1][i] && ddn[i] == 3)
            di[2] = i;
    }
    bfs(2);
    for(int i = 1; i <= n; ++i)//得到x, y
    {
        poi[i].x = (dist[0][i] + dist[2][i] - ((tn-1)<<1)) >> 1;
        poi[i].y = (dist[0][i] - poi[i].x - poi[i].z) + 1;
        poi[i].x++;
        poi[i].y++;
        mmap[poi[i].x][poi[i].y][poi[i].z] = i;
    }
    dfs(1, 0);
    cout << minn << ' ' << maxx << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}