luogu#P3342. [ZJOI2014] 璀灿光华

    ID: 7372 远端评测题 1000~1500ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2014浙江枚举暴力广度优先搜索BFS图的建立建图

[ZJOI2014] 璀灿光华

题目描述

金先生有一个女朋友没名字。她勤劳勇敢、智慧善良。金先生很喜欢她。为此,金先生用 a3a^31×1×11\times 1 \times 1 的独特的水晶制作了一个边长为 aa 的水晶立方体,他要将这个水晶立方体送给他见过最单纯善良的她。

由于水晶立方体太太,不好运送,金先生还是将它拆开来送出。他相信拼好这个水晶立方难不倒聪明的她。

没名字收到了礼物后果然不一会儿就根据说明将水晶立方体拼好了。没名字发现,有 nn 块水晶在漆黑安静的夜晚会随机以等概率向上下左右前后六个方向的一个发出穿透光。被光照到的水晶显得格外好看。没名字给每一块不会发光的水晶定义了一个好看程度。水晶立方体在夜晚中的好看程度就是每块被光照到的水晶的好看程度之和。没名字想知道,水晶立方体在夜晚中的好看程度的最小值和最大值。

输入格式

第一行是 aa,表示水晶立方体的边长。 接下来 a3a^3 行,每行若干整数。 第一个数 gig_i 表示第 ii 块水晶的好看程度。如果 gi=0g_i=0,代表这块水晶会发光。接下来 363\sim 6 个整数,代表与这块水晶有共同面的水晶编号。

输出格式

两个整数,代表水晶立方体在夜晚好看程度的最小值与最大值。

2
0 7 2 3
0 8 1 4
4 5 4 1
8 6 3 2
16 3 6 7
32 4 5 8
1 1 8 5
2 2 7 6
0 12

提示

对于所有数据,1<a701<a\leq 70gi<106g_i<10^6n8n\leq 8