1 #include <iostream> 2 #include <cstdio> 3 #include <climits> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #include <vector> 8 #include <queue> 9 #include <algorithm> 10 #define esp 1e-6 11 #define pb push_back 12 #define in freopen("in.txt", "r", stdin); 13 #define out freopen("out.txt", "w", stdout); 14 #define print(a) printf("%d ",(a)); 15 #define bug puts("********))))))"); 16 #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) 17 #define inf 0x0f0f0f0f 18 using namespace std; 19 typedef long long LL; 20 typedef vector<int> VI; 21 typedef vector<int>:: iterator IT; 22 typedef pair<int, int> pii; 23 #define N 300 24 int x[N], y[N], z[N]; 25 int G[N][N], dp[N]; 26 int n; 27 int f(int i) 28 { 29 int ans = dp[i]; 30 if(ans > 0) 31 return ans; 32 ans = z[i]; 33 for(int j = 1; j <= n*3; j++) 34 if(G[i][j]) 35 ans = max(ans, f(j)+z[i]); 36 return dp[i] = ans; 37 } 38 bool check(int i, int j) 39 { 40 return (x[i]>x[j] && y[i] > y[j]) || (x[i] > y[j] && y[i] > x[j]); 41 } 42 int main(void) 43 { 44 int t =1; 45 while(scanf("%d", &n), n) 46 { 47 memset(dp, -1, sizeof(dp)); 48 memset(G, 0, sizeof(G)); 49 for(int i = 1; i <= n; i++) 50 { 51 scanf("%d%d%d", x+i, y+i, z+i); 52 x[n+i] = z[i], y[n+i] = x[i], z[n+i] = y[i]; 53 x[2*n+i] = y[i], y[2*n+i] = z[i], z[2*n+i] = x[i]; 54 } 55 for(int i = 1; i <= n*3; i++) 56 for(int j = 1; j <= n*3; j++) 57 { 58 if(check(i,j)) 59 G[i][j] = 1; 60 } 61 int ans = 0; 62 for(int i = 1; i <= n*3; i++) 63 ans = max(ans, f(i)); 64 printf("Case %d: maximum height = %d ", t, ans); 65 t++; 66 } 67 return 0; 68 }
上面的是普通dp做法，将每种砖头，拆成3个点，分别表示不同的高度，然后不同的砖头（i，j），如果j能放到i上面，那么建一条边从i->j,权重为j的高z[j],由于最下层可能为任何一块砖头，的任何一面作为塔的底部，可以从0分别建立一条到所有砖头i的边，权重为z[i]，这样问题转化为求从源点src = 0，出发的最长路径了，类比最短路的做法，可以用spfa，基于优先队列的dijkstra。
代码：
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pb push_back
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d
",(a));
#define bug puts("********))))))");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<int>:: iterator IT;
typedef pair<int, int> pii;
#define N 100
#define M 10000
struct EDGE
{
int i, c;
EDGE *next, *ani;
} *Edge[N], E[M];
int x[N], y[N], z[N];
int cnt, dis[N];
VI dist;
void add(int i, int j, int c, EDGE &e1)
{
e1.i = j, e1.c = c, e1.next = Edge[i], Edge[i] = &e1;
// e2.i = i, e2.c = c, e2.ani = &e1, e2.next = Edge[j], Edge[j] = &e2;
cnt++;
}
bool check(int i, int j)
{
return (x[i] > x[j] && y[i] > y[j]) || (x[i] > y[j] && y[i] > x[j]);
}
void init(void)
{
memset(Edge, 0, sizeof(Edge));
cnt = 0;
}
void spfa(int src)
{
int inq[N];
memset(inq, 0, sizeof(inq));
queue<int> q;
q.push(src);
inq[src] = 1;
while(!q.empty())
{
int u = q.front();
q.pop();
inq[u] = 0;
int v;
for(EDGE *p = Edge[u]; p; p = p->next)
{
if(dist[v = p->i] < dist[u] + p->c)
if(dist[v] = dist[u] + p->c, !inq[v])
inq[v] = 1 , q.push(v);
}
}
}
int main(void)
{
int t = 1;
int n;
while(scanf("%d", &n), n)
{
init();
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d", x+i, y+i, z+i);
x[n+i] = y[i], y[n+i] = z[i], z[n+i] = x[i];
x[2*n+i] = x[i], y[2*n+i] = z[i], z[2*n+i] = y[i];
}
for(int i = 1; i <= n*3; i++)
{
for(int j = 1; j <= n*3; j++)
if(check(i,j))
add(i, j, z[j], E[cnt]);
add(0, i, z[i], E[cnt]);
}
dist.clear();
// dist.resize(3*n+1);
for(int i = 0; i <= 3*n; i++)
dist[i] = 0;
spfa(0);
printf("Case %d: maximum height = %d
", t, *max_element(dist.begin(), dist.end()));
t++;
}
return 0;
}
dijkstra：
1 #include <iostream> 2 #include <cstdio> 3 #include <climits> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #include <vector> 8 #include <queue> 9 #include <algorithm> 10 #define esp 1e-6 11 #define pb push_back 12 #define in freopen("in.txt", "r", stdin); 13 #define out freopen("out.txt", "w", stdout); 14 #define print(a) printf("%d ",(a)); 15 #define bug puts("********))))))"); 16 #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) 17 #define inf 0x0f0f0f0f 18 using namespace std; 19 typedef long long LL; 20 typedef vector<int> VI; 21 typedef vector<int>:: iterator IT; 22 typedef pair<int, int> pii; 23 using namespace std; 24 #define N 100 25 #define M 10000 26 struct EDGE 27 { 28 int i, c; 29 EDGE *next, *ani; 30 } *Edge[N], E[M]; 31 int x[N], y[N], z[N]; 32 int cnt, dis[N]; 33 VI dist; 34 void add(int i, int j, int c, EDGE &e1) 35 { 36 e1.i = j, e1.c = c, e1.next = Edge[i], Edge[i] = &e1; 37 // e2.i = i, e2.c = c, e2.ani = &e1, e2.next = Edge[j], Edge[j] = &e2; 38 cnt++; 39 } 40 bool check(int i, int j) 41 { 42 return (x[i] > x[j] && y[i] > y[j]) || (x[i] > y[j] && y[i] > x[j]); 43 } 44 void init(void) 45 { 46 memset(Edge, 0, sizeof(Edge)); 47 cnt = 0; 48 } 49 struct cmp 50 { 51 bool operator () (const pii a, const pii b) 52 { 53 return a.first < b.first; 54 } 55 }; 56 void dij(void) 57 { 58 priority_queue<pii, vector<pii> ,cmp > q; 59 q.push(make_pair(0, 0)); 60 while(!q.empty()) 61 { 62 pii u = q.top(); 63 int x = u.second; 64 q.pop(); 65 int y; 66 if(dist[x] == u.first) 67 { 68 for(EDGE *p = Edge[x]; p; p = p->next) 69 { 70 if(dist[y = p->i] < dist[x] + p->c) 71 { 72 dist[y] = dist[x] + p->c; 73 q.push(make_pair(dist[y], y)); 74 } 75 } 76 } 77 } 78 } 79 int main(void) 80 { 81 82 int t = 1; 83 int n; 84 while(scanf("%d", &n), n) 85 { 86 init(); 87 for(int i = 1; i <= n; i++) 88 { 89 scanf("%d%d%d", x+i, y+i, z+i); 90 x[n+i] = y[i], y[n+i] = z[i], z[n+i] = x[i]; 91 x[2*n+i] = x[i], y[2*n+i] = z[i], z[2*n+i] = y[i]; 92 } 93 for(int i = 1; i <= n*3; i++) 94 { 95 for(int j = 1; j <= n*3; j++) 96 if(check(i,j)) 97 add(i, j, z[j], E[cnt]); 98 add(0, i, z[i], E[cnt]); 99 } 100 dist.clear(); 101 dist.resize(3*n+1); 102 // for(int i = 0; i <= 3*n; i++) 103 // dist[i] = 0; 104 dij(); 105 printf("Case %d: maximum height = %d ", t, *max_element(dist.begin(), dist.end())); 106 t++; 107 } 108 return 0; 109 }