首页 > 代码库 > 旅行-树形DP
旅行-树形DP
60分:对于每个点为根的情况做一遍DP,s,g表示从小C,A从这个点走出去的路程
100分,树形DP对于每个点的路径可以由其父亲转来,这样的DP就需要比较好的技巧了。
以前有道差不多的叫星座的题目来着。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define ll long long int n,x,y,z,num;int head[300005],next[600005],to[600005],val[600005];ll f[300005],g[300005],fs[300005],gs[300005],ans[300005]; void add_edge(int u,int v,int c){ to[++num]=v; val[num]=c; next[num]=head[u]; head[u]=num; }void dp(int u,int fa){ bool son=0; for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { son=1; dp(to[edge],u); f[u]=max(f[u],g[to[edge]]+val[edge]); g[u]=min(g[u],f[to[edge]]+val[edge]); } if(!son) g[u]=0; }void DP(int u,int fa){ ll s1=1e16,s2=1e16; int p1=0,p2=0; for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { if(f[to[edge]]+val[edge]<s1) { s2=s1; s1=f[to[edge]]+val[edge]; p2=p1; p1=to[edge]; }else if(f[to[edge]]+val[edge]<s2) { s2=f[to[edge]]+val[edge]; p2=to[edge]; } } for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { if(p1!=to[edge]) fs[to[edge]]=min(fs[to[edge]],s1+val[edge]);else fs[to[edge]]=min(fs[to[edge]],s2+val[edge]); fs[to[edge]]=min(fs[to[edge]],gs[u]+val[edge]); } ll g1=0,g2=0; p1=0,p2=0; for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { if(g[to[edge]]+val[edge]>g1) { g2=g1; g1=g[to[edge]]+val[edge]; p2=p1; p1=to[edge]; }else if(g[to[edge]]+val[edge]>g2) { g2=g[to[edge]]+val[edge]; p2=to[edge]; } } for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { if(p1!=to[edge]) gs[to[edge]]=max(gs[to[edge]],g1+val[edge]);else gs[to[edge]]=max(gs[to[edge]],g2+val[edge]); gs[to[edge]]=max(gs[to[edge]],fs[u]+val[edge]); } for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { ans[to[edge]]=max(fs[to[edge]],f[to[edge]]); DP(to[edge],u); } } int main(){ scanf("%d",&n); for(int i=1;i<=n-1;i++) { int u,v,c; scanf("%d %d %d",&u,&v,&c); add_edge(u,v,c); add_edge(v,u,c); } memset(g,127,sizeof(g)); dp(1,0); memset(fs,127,sizeof(fs)); ans[1]=f[1];gs[1]=1e6;fs[1]=0; DP(1,0); for(int i=1;i<=n;i++) cout<<ans[i]<<endl;}
旅行-树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。