#P2241. The Tower of Babylon

The Tower of Babylon

中文题面:

描述

也许你曾听说过巴比伦塔的传说。如今,这个故事的许多细节已被遗忘。因此,本着本次竞赛的教育性质,我们将为你讲述完整的故事:

巴比伦人拥有nn种类型的积木,每种类型的积木供应无限。每种类型ii的积木是一个尺寸为(xi,yi,zi)(x_i, y_i, z_i)的长方体。积木可以重新定向,使得其任意两个维度决定底座的尺寸,另一个维度决定高度。

他们希望通过堆叠积木建造尽可能高的塔。问题是,在建塔时,一个积木只能放在另一个积木的顶部,且上方积木的两个底座维度必须严格小于下方积木对应的底座维度。这意味着,如果两个积木的底座尺寸相同,则不能堆叠。

你的任务是编写一个程序,计算巴比伦人用给定积木可以建造的最高塔的高度。

输入

输入包含一个或多个测试用例。每个测试用例的第一行是一个整数nn,表示接下来数据集中不同积木的数量。nn的最大值为3030

接下来的nn行,每行包含三个整数,分别表示xix_iyiy_iziz_i的值。

输入以n=0n=0终止。

输出

对于每个测试用例,输出一行,包含用例编号(从1开始顺序编号)和最高塔的高度,格式为:
"Case 用例编号: maximum height = 高度"

输入数据 1

1  
10 20 30  
2  
6 8 10  
5 5 5  
7  
1 1 1  
2 2 2  
3 3 3  
4 4 4  
5 5 5  
6 6 6  
7 7 7  
5  
31 41 59  
26 53 58  
97 93 23  
84 62 64  
33 83 27  
0  

输出数据 1

Case 1: maximum height = 40  
Case 2: maximum height = 21  
Case 3: maximum height = 28  
Case 4: maximum height = 342