首页 > 代码库 > POJ 3728
POJ 3728
题意：
一个树形图，有个二货商人，旅游时候还想着赚钱！从某个地方到另一个地方时，可以旅途中进一批货（应该人手不够，手里只能拿一批），然后在旅途中卖掉，求最大能赚多少钱。
思路：
赤裸裸的LCA，ans(x,y)=max(up(x,lca),down(lca,y),maxp(lca,y)-min(lca,x));
注意每次更新要在父亲节点处更新，繁琐了些。还是多用用STL吧！
竟然犯了一个无语的RE，忘了是双向边。去切腹吧 — 。—
代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))using namespace std;long long maxp[50005],minp[50005],up[50005],down[50005];int be[50005],all;int bq[50005],qall;long long question[50005][3];int f[50005];bool vis[50005];int x,y,n,q;struct Edge{ int y,ne;}e[150005];struct Query{ int y,res,ne;}query[150005];vector<int> num[50005];void add(int x, int y){ e[all].y=y; e[all].ne=be[x]; be[x]=all++; e[all].y=x; e[all].ne=be[y]; be[y]=all++;}void qadd(int x, int y, int i){ query[qall].y=y; query[qall].res=i; query[qall].ne=bq[x]; bq[x]=qall++; query[qall].y=x; query[qall].res=i; query[qall].ne=bq[y]; bq[y]=qall++;}int find(int x){ int oldf=f[x]; if(f[x]!=x) f[x]=find(f[x]); up[x]=max(max(up[x],up[oldf]),maxp[oldf]-minp[x]); down[x]=max(max(down[x],down[oldf]),maxp[x]-minp[oldf]); maxp[x]=max(maxp[oldf],maxp[x]); minp[x]=min(minp[oldf],minp[x]); return f[x];}void tarjan(int u){ vis[u]=1; for(int i=be[u]; i!=-1; i=e[i].ne) { int v=e[i].y; if(!vis[v]) { tarjan(v); f[v]=u; } } for(int i=bq[u]; i!=-1; i=query[i].ne) if(vis[query[i].y]) { int fx=find(query[i].y); num[fx].push_back(query[i].res); } for(vector<int>::iterator it=num[u].begin(); it!=num[u].end(); it++) { int x=question[*it][0], y=question[*it][1]; find(x); find(y); question[*it][2]=max(max(up[x],down[y]),maxp[y]-minp[x]); }}int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&x); minp[i]=maxp[i]=x; up[i]=down[i]=0; f[i]=i; } memset(be,-1,sizeof(be)); memset(bq,-1,sizeof(bq)); all=qall=0; memset(vis,0,sizeof(vis)); for(int i=1; i<=n-1; i++) { scanf("%d%d",&x,&y); add(x,y); } scanf("%d",&q); for(int i=1; i<=q; i++) { scanf("%d%d",&x,&y); qadd(x,y,i); question[i][0]=x; question[i][1]=y; question[i][2]=0; } tarjan(1); for(int i=1; i<=q; i++) printf("%d\n",question[i][2]); return 0;}
还能用RMQ做，待我取经回来再搞一发！
POJ 3728
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。