uva 437 - The Tower of Babylon(DAG最长路)

本文出自 http://blog.csdn.net/shuangde800

题目：点击打开链接

题目大意

有n种长宽高为x,y,z的砖头，每种都有无数个。

砖头可以用不同姿势的方向来盖。

砖头a以某种姿势可以盖在砖头b上，当且仅当a的底部的长宽都要比b的底部长宽要小。

问最高可以建多高？

思路

对于一个x,y,z砖头，它可以有3中姿势放置。

(前两个为地面，后一个为高)

x, y, z

x, z, y

y, z, x

把每种姿势都记录下来，变成了有3*n种固定姿势的砖头。

然后建图，g[i][j] = true, 表示砖头i可以盖在砖头j上，反之亦然。

然后就是求dag上的最长路了。

代码

<script src="https://code.csdn.net/snippets/567.js" type="text/javascript"></script>