101550h专题

Highest Tower Gym - 101550H(建图,思路)

题意: n个矩形,要求使得上面矩形宽度严格小于下面矩形,问能够得到的最大高度。 思路: 很巧妙的思路。 首先题目保证一定有解。考虑将每个矩形的边(u,v)设置双向边u->v与v->u,u->v代表选择u为宽,v为高。那么可以建出一张图,这个图可以分出很多连通分量,不同连通分量意味着每个边都是不同的,那么可以在两个连通分量内分别堆成最高的矩形,然后将两者合并,结果仍然最优。所以对连通分量可以分