首页 > 代码库 > 动态规划(树形DP):HDU 5834 Magic boy Bi Luo with his excited tree
动态规划(树形DP):HDU 5834 Magic boy Bi Luo with his excited tree
非常难想的树形DP。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N=100010; 6 int cnt,fir[N],nxt[N*2],to[N*2],val[N*2]; 7 int n,w[N],ans[N],fa[N],f1[N][2],f2[N][2]; 8 void addedge(int a,int b,int v){ 9 nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;val[cnt]=v;10 nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;val[cnt]=v;11 }12 13 void DFS(int x){int ret=0;14 f1[x][0]=f1[x][1]=w[x];15 for(int i=fir[x];i;i=nxt[i])16 if(to[i]!=fa[x]){17 fa[to[i]]=x;DFS(to[i]);18 f1[to[i]][0]=max(f1[to[i]][0]-val[i],0);19 f1[to[i]][1]=max(f1[to[i]][1]-val[i]*2,0);20 ret=max(ret,f1[to[i]][0]-f1[to[i]][1]);21 f1[x][1]+=f1[to[i]][1];22 }23 f1[x][0]=f1[x][1]+ret; 24 }25 26 void DP(int x){27 int ret=w[x],v1=0,v2=0,p=0;28 if(fa[x]){29 ret+=f2[x][1];30 int tmp=f2[x][0]-f2[x][1];31 if(tmp>v1)v2=v1,v1=tmp;32 else if(tmp>v2)v2=tmp;33 }34 for(int i=fir[x];i;i=nxt[i])35 if(to[i]!=fa[x]){36 ret+=f1[to[i]][1];37 int tmp=f1[to[i]][0]-f1[to[i]][1];38 if(tmp>v1)v2=v1,v1=tmp,p=to[i];39 else if(tmp>v2)v2=tmp;40 }41 ans[x]=ret+v1;42 for(int i=fir[x];i;i=nxt[i])43 if(to[i]!=fa[x]){44 f2[to[i]][1]=ret-f1[to[i]][1]-val[i]*2;45 if(to[i]!=p)f2[to[i]][0]=f2[to[i]][1]+v1+val[i];46 else f2[to[i]][0]=f2[to[i]][1]+v2+val[i];47 f2[to[i]][0]=max(f2[to[i]][0],0);48 f2[to[i]][1]=max(f2[to[i]][1],0);49 DP(to[i]);50 }51 }52 53 void Init(){54 memset(fir,0,sizeof(fir));55 memset(f1,0,sizeof(f1));56 memset(f2,0,sizeof(f2));57 memset(fa,0,sizeof(fa));58 cnt=0;59 }60 61 int T,cas;62 int main(){63 scanf("%d",&T);64 while(T--){65 Init();66 scanf("%d",&n);67 for(int i=1;i<=n;i++)scanf("%d",&w[i]);68 for(int i=1,a,b,v;i<n;i++){69 scanf("%d%d%d",&a,&b,&v);70 addedge(a,b,v);71 }72 DFS(1);DP(1);73 printf("Case #%d:\n",++cas);74 for(int i=1;i<=n;i++)75 printf("%d\n",ans[i]);76 }77 return 0;78 }
动态规划(树形DP):HDU 5834 Magic boy Bi Luo with his excited tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。