hdu 5834 Magic boy Bi Luo with his excited tree 树形dp
发布时间:2020-12-14 01:37:14 所属栏目:大数据 来源:网络整理
导读:题目大意:给定一个树。给个点有一个值,每个边也有一个值,经过点可以得到点的值(只能拿一次),边每次经过都要减去边的值。可以理解为点有钱,经过边要交路费,问从每个点开始,得到的值最大是多少。 题解:PS(感觉像是一道以前CF的题,但是找了很久也没有
题目大意:给定一个树。给个点有一个值,每个边也有一个值,经过点可以得到点的值(只能拿一次),边每次经过都要减去边的值。可以理解为点有钱,经过边要交路费,问从每个点开始,得到的值最大是多少。 题解:PS(感觉像是一道以前CF的题,但是找了很久也没有找到) 由于要输出每一个点,所以很自然地想到树形dp。 我们可以先以1为root,以f[i][0]表示在i的子树下返回i所能得到的最大值,以f[i][1]表示在i的子树下不返回i所能得到的最大值。 可以处理掉所有的子树的问题。然而在当前节点与父节点相连时会出现当前边就是父节点(不返回时)最优的走法,所以我们要记录并维护当前(不返回时)次优的解法。(最优和次优必须是无重合的两条路径)。然后再对当前边与f[i][0]和f[i][1]进行分类讨论。代码中g[i]表示返回i点所能得到的最大值,f[i][0]代表不返回i的最大值,f[i][1]代表不返回i的次大值,path记录其对应的是那条边。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; #define maxn 200100 int g[maxn],f[maxn][2],path[maxn][2],val[maxn],v[maxn],n,en; int first[maxn],nex[maxn],to[maxn]; const int read() { char ch = getchar(); while (ch<'0' || ch>'9') ch = getchar(); int x = ch - '0'; while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0'; return x; } void add(int a,int b,int c) { en++; to[en]=b; nex[en]=first[a]; first[a]=en; val[en]=c; } void dfs(int fa,int now) { int u; g[now]=v[now]; path[now][0]=path[now][1]=-1; int tmp; for(int i=first[now];i;i=nex[i]) { u=to[i]; if(u==fa) continue; dfs(now,u); g[now]+=max(0,g[u]-val[i]*2); } for(int i=first[now];i;i=nex[i]) { u=to[i]; if(u==fa||f[u][0]<=val[i]) continue; tmp=g[now]-max(g[u]-2*val[i],0)+max(f[u][0]-val[i],0); if(path[now][0]==-1) path[now][0]=i,f[now][0]=tmp; else if (path[now][1]==-1 || f[now][1] < tmp) { path[now][1]=i; f[now][1]=tmp; if (f[now][0] < f[now][1]) swap(f[now][0],f[now][1]),swap(path[now][0],path[now][1]); } } if (path[now][1] == -1) f[now][1]=g[now]; if (path[now][0] == -1) f[now][0]=g[now]; } void dfs2(int fa,int now) { int u; int tmp=0,kk=0,flag; for(int i=first[now];i;i=nex[i]) { u=to[i]; if(u==fa) continue; f[u][0] = f[u][0] + max(g[now] - max(g[u]-2*val[i],0)-2*val[i],0); f[u][1] = f[u][1] + max(g[now] - max(g[u]-2*val[i],0); flag = i; if(g[u]>=val[i]*2) { if(path[now][0]!=i) tmp=f[now][0]+val[i]; else tmp=f[now][1]+val[i]; } else { if(path[now][0]!=i) tmp=g[u]-val[i]+f[now][0]; else tmp=g[u]-val[i]+f[now][1]; } if (f[u][1] <= tmp) swap(f[u][1],tmp),swap(path[u][1],flag); if (f[u][0] <= f[u][1]) swap(f[u][0],f[u][1]),swap(path[u][0],path[u][1]); g[u]+=max(g[now] - max(g[u]-2*val[i],0); dfs2(now,u); } } int main() { int a,b,c; int cas; scanf("%d",&cas); for(int i=1;i<=cas;i++) { printf("Case #%d:n",i); en=0; memset(first,sizeof(first)); scanf("%d",&n); for(int i=1;i<=n;i++) v[i]=read(); for(int i=1;i<n;i++) { a=read(); b=read(); c=read(); add(a,c); add(b,a,c); } dfs(0,1); dfs2(0,1); for(int i=1;i<=n;i++) { printf("%dn",f[i][0]); } } return 0; } /* 1 5 4 1 7 7 7 1 2 6 1 3 1 2 4 8 3 5 2 */ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |