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 = ;

int C[N][];

int d[N][];

bool vis[N][];

int trans[][];

int main()

{

    //freopen("in.txt","r",stdin);

    for(int i = ; i < ; i++){

        int t = ;

        for(int j = ; j < ; j++)if(i!=j){

            trans[i][t++] = j;

        }

    }

    int kas = ,n;

    while(scanf("%d",&n),n){

        for(int i = ; i < n; i++){

            scanf("%d%d%d",d[i],d[i]+,d[i]+);

            sort(d[i],d[i]+);

            memcpy(C[i],d[i],sizeof(int)*);

        }

        queue<pii> q;

        for(int i = ; i < n; i++){

            for(int j = ; j < ; j++){

                q.push(MP(i,j)); vis[i][j] = true;

            }

        }

        int Hei = ;

        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][]], W = C[id][trans[k][]];

            if(H>W) swap(H,W);

            for(int i = ; i < n; i++){

                for(int j = ; j < ; j++){

                    int h = C[i][trans[j][]], w = C[i][trans[j][]];

                    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\n",++kas,Hei);

    }

    return ;

}