题解 UVA437
每种方块都可以将 \(x\times y,x\times z,y\times z\) 的面放在水平面上，所以每块都有 \(3\) 种状态，每次从剩余所有 \(n-1\) 个块的 \(3\) 种状态中选取能放置在此方块上方的方块，（即选取水平面矩形对应的边小于当前水平面边权），并且由大面积的块向小面积的块连边。
连好后直接考虑 \(dp\) ，\(dp_v=\underset {(u,v)\in E}{\max}\{dp_v,dp_u+w_{u,v}\}\) 。
直接拓扑排序即可。
\(\tt tips:\) 每条边的边权设为有向边指向的方块的高度，因为相当于点权转边权，应增加一个编号为 \(0\) 的节点，指向所有方块的 \(3\) 种情况，并且每条边的边权设为这些方块 \(3\) 种情况的高度。同时因为是连边时判断罗列关系，所以为了保证 \(0\) 号节点在最底部，应将其长宽都设为最大，并且高度为 \(0\) 消除影响，具体实现见代码。
提供一组数据：
10
38 29 47
18 13 19
30 31 91
78 92 92
83 1 78
58 88 5
32 82 25
34 47 50
44 49 72
97 24 71
out:458
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
const int N=10000;
int T,n,m,cnt,ans,tot,ton;
int head[N<<3],f[N<<3],du[N<<3];
queue<int> q;
struct Node{
int u,v,h;
bool friend operator < (Node a,Node b){
if(a.u<b.u && a.v<b.v) return 1;
return 0;
}//重载运算符，方便进行结构体比较
}e[N<<3];
struct node{
int to,nxt,w;
}edge[N<<4];
int read(){
int f=1,res=0;char c=getchar();
while(c>'9' || c<'0') c=='-'?f*=-1:f=f,c=getchar();
while(c>='0' && c<='9') res=res*10+c-'0',c=getchar();
return res*f;
}
void add(int x,int y){
//进行比较，确定罗列关系
if(e[y]<e[x]) edge[++cnt]=((node){y,head[x],e[y].h}),head[x]=cnt,du[y]++;
else if(e[x]<e[y]) edge[++cnt]=((node){x,head[y],e[x].h}),head[y]=cnt,du[x]++;
//记录入度数，拓扑排序
return ;
}
void topsort(){
while(q.size()) q.pop();
for(int i=0;i<=3*n;i++) if(!du[i]) q.push(i);
while(q.size()){
int t=q.front();q.pop();
for(int i=head[t];i;i=edge[i].nxt){
if(!--du[edge[i].to]) q.push(edge[i].to);
f[edge[i].to]=max(f[edge[i].to],f[t]+edge[i].w);
ans=max(ans,f[edge[i].to]);
}
}
}
int main(){
while(1){
n=read();if(!n) break ;
cnt=0,ans=0,ton=0;
memset(head,0,sizeof head);
memset(f,0,sizeof f);
e[0]=((Node){1000000000,1000000000,0});//编号为 0 的节点
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[++ton]=((Node){min(x,y),max(x,y),z});
e[++ton]=((Node){min(x,z),max(x,z),y});
e[++ton]=((Node){min(y,z),max(y,z),x});
//讨论 3 种情况
}
for(int i=1;i<=ton;i++) for(int j=0;j<i;j++) add(i,j);//加边
topsort();//拓扑排序，同时进行 dp
printf("Case %d: maximum height = %d\n",++tot,ans);
}
return 0;
}