Packing Unit 4D Cubes

http://acm.pku.edu.cn/JudgeOnline/problem?id=1022
久しぶりに普通に解いてみました。「4D」というタイトルの通り4次元を扱う問題ではありますが、2次元から3次元・4次元へと拡張すれば、それほど難しくはありません。

2次元のイメージで概要を説明しておきます。

同じ大きさの物体の隣接関係がデータとして与えられます。与えられた隣接関係の通りに物体を配置し、それをシンプルな箱で包むとすれば、箱の大きさの最小値はいくつになるのかを求めます。ただし、隣接関係のデータに矛盾がある場合もあるので、矛盾の無いデータに関してのみ最小値を計算します。

ポイントは次元の拡張と探索木の生成ってところでしょうか。またもやウンコなテストデータということでショートコーディングには向いてないですが、普通に解くにはまずまずのレベルではないでしょうか。