写到现在，发现1025,1076之前写的都是同一种题型：关于DAG的最长路（最短路）。
首先要建立模型，根据关系，确定点和点之间的关系，构成一个DAG，前面几道题每个点之间距离默认为1，这一道题不同点之间距离不一样.然后进行拓扑（最基本，稳健方法）或者直接贪心乱搞，求出最长路或是最短路。
数据比较弱吧，都是0ms跑完的。
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<iostream> #include<cstring> #include<queue> #include<vector> using namespace std; #define LL long long struct node { int x,y,z; }a[200]; LL dp[200]; int deg[200]; vector<int> t[200]; int n; void pre(int n,int xx,int yy,int zz) { a[n*6].x=xx; a[n*6].y=yy; a[n*6].z=zz; a[n*6+1].x=xx; a[n*6+1].y=zz; a[n*6+1].z=yy; a[n*6+2].x=yy; a[n*6+2].y=xx; a[n*6+2].z=zz; a[n*6+3].x=yy; a[n*6+3].y=zz; a[n*6+3].z=xx; a[n*6+4].x=zz; a[n*6+4].y=yy; a[n*6+4].z=xx; a[n*6+5].x=zz; a[n*6+5].y=xx; a[n*6+5].z=yy; } LL ans; queue<int> q; void tp() { ans=0; while(!q.empty()) q.pop(); for(int i=0;i<6*n;i++) { if(deg[i]==0) { q.push(i); dp[i]=a[i].z; } } while(!q.empty()) { int x=q.front(); ans=max(ans,dp[x]); q.pop(); for(int i=0;i<t[x].size();i++) { int f=t[x][i]; deg[f]--; dp[f]=max(dp[f],dp[x]+a[f].z); if(deg[f]==0) q.push(f); } } } int main() { //freopen("input.txt","r",stdin); int cas=1; while(scanf("%d",&n)==1&&n) { int x,y,z; memset(deg,0,sizeof(deg)); memset(dp,0,sizeof(dp)); for(int i=0;i<6*n;i++) t[i].clear(); for(int i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&z); pre(i,x,y,z); } for(int i=0;i<6*n;i++) for(int j=0;j<6*n;j++) { if(a[i].x<a[j].x&&a[i].y<a[j].y) { t[j].push_back(i); deg[i]++;//入度 } } tp(); printf("Case %d: maximum height = %lld ",cas++,ans); } }