巴比伦塔 The Tower of Babylon

题意翻译

【题目】 你可能已经听说过巴比伦塔的传说。现在这个传说的许多细节已经被遗忘。所以本着本场比赛的教育性质,我们现在会告诉你整个传说: 巴比伦人有n种长方形方块,每种有无限个,第i种方块的三边边长是xi,yi,zi。对于每一个方块,你可以任意选择一面作为底,这样高就随着确定了。举个例子,同一种方块,可能其中一个是竖着放的,一个是侧着放的,一个是横着放的。 他们想要用堆方块的方式建尽可能高的塔。问题是,只有一个方块的底的两条边严格小于另一个方块的底的两条边,这个方块才能堆在另一个上面。这意味着,一个方块甚至不能堆在一个底的尺寸与它一样的方块的上面。 你的任务是编写一个程序,计算出这个塔可以建出的最高的高度。 【输入】 输入会包含至少一组数据,每组数据的第一行是一个整数n(n<=30),表示方块的种类数。 这组数据接下来的n行,每行有三个整数,表示xi,yi,zi。 输入数据会以0结束。 【输出】 对于每组数据,输出一行,其中包含组号(从1开始)和塔最高的高度。按以下格式: Case : maximum height = __ 【输入样例】 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 【输出样例】 Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=378 [PDF](https://uva.onlinejudge.org/external/4/p437.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA437/9cfd091ffcf425df6dc3f975c119a7baf8b0d379.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA437/c1b55febc01cfad1e18e1ddbf4d0b7f0160a6980.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA437/2a1d77dbe3a0a30c7bbc7ad5f7d1ce69e94eb6b8.png)

输入输出样例

输入样例 #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