UVA 427 The Tower of Babylon 巴比伦塔（dp）

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

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

#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define fi first
#define se second
typedef pair<int,int> 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<pii> 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<H&&w<W && d[i][j] < C[i][j]+d[id][k]){
                        d[i][j] = C[i][j]+d[id][k];
                        if(!vis[i][j]){
                            q.push(MP(i,j)); vis[i][j] = true;
                        }
                    }

                }
            }
            q.pop();
        }
        printf("Case %d: maximum height = %d
",++kas,Hei);
    }
    return 0;
}