据说是DAG的dp，可用spfa来做，松弛操作改成变长。注意状态的表示。

影响决策的只有顶部的尺寸，因为尺寸可能很大，所以用立方体的编号和高的编号来表示，然后向尺寸更小的转移就行了。

#include
     
      using namespace std;#define MP make_pair#define fi first#define se secondtypedef pair
      
        pii;const int N = 42;int C[N][3];int d[N][3];bool vis[N][3];int trans[3][2];int main(){    //freopen("in.txt","r",stdin);    for(int i = 0; i < 3; i++){        int t = 0;        for(int j = 0; j < 3; j++)if(i!=j){            trans[i][t++] = j;        }    }    int kas = 0,n;    while(scanf("%d",&n),n){        for(int i = 0; i < n; i++){            scanf("%d%d%d",d[i],d[i]+1,d[i]+2);            sort(d[i],d[i]+3);            memcpy(C[i],d[i],sizeof(int)*3);        }        queue
       
         q;        for(int i = 0; i < n; i++){            for(int j = 0; j < 3; j++){                q.push(MP(i,j)); vis[i][j] = true;            }        }        int Hei = 0;        while(q.size()){            pii &u = q.front();            int id = u.fi,k = u.se;            vis[id][k] = false;            Hei = max(Hei,d[id][k]);            int H = C[id][trans[k][0]], W = C[id][trans[k][1]];            if(H>W) swap(H,W);            for(int i = 0; i < n; i++){                for(int j = 0; j < 3; j++){                    int h = C[i][trans[j][0]], w = C[i][trans[j][1]];                    if(h>w) swap(h,w);                    if(h