|
【HDOJ 5834】Magic boy Bi Luo with his excited tree（树型DP）
Magic boy Bi Luo with his excited tree
Time Limit: 8000/4000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)
Problem Description
Bi Luo is a magic boy,he also has a migic tree,the tree has N nodes,in each node,there is a treasure,it’s value is V[i],and for each edge,there is a cost C[i],which means every time you pass the edge i,you need to pay C[i].
You may attention that every V[i] can be taken only once,but for some C[i],you may cost severial times.
Now,Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i.
Bi Luo is also an excited boy,now he wants to know every ans[i],can you help him?
?
Input
First line is a positive integer
T(T≤104)
,represents there are
T
test cases.
Four each test：
The first line contain an integer N
(N≤105)
.
The next line contains N integers V[i],which means the treasure’s value of node
i(1≤V[i]≤104)
.
For the next N - 1 lines,each contains three integers u,v,c,which means node u and node v are connected by an edge,it’s cost is
c(1≤c≤104)
.
You can assume that the sum of N will not exceed
106
.
?
Output
For the i-th test case,first output Case #i: in a single line,then output ans[i] in a single line.
?
Sample Input
1
5
4 1 7 7 7
1 2 6
1 3 1
2 4 8
3 5 2
?
Sample Output
Case #1:
15
10
14
9
15
?
Author
UESTC
?
Source
2016中国大学生程序设计竞赛 - 网络选拔赛
题目大意：
一棵树，节点有价值，树边有花费。
节点价值只能get到一次，树边花费每次经过都要消耗。
输出从节点1~n出发，分别能得到的最大净价值(节点收获-树边花费)
一眼树型dp
可能是做树dp做多了有感觉了，或者是因为训练计划上类似的题较多，。
首先考虑子问题：
节点1做根，输出最大价值。
令
dp[u][0]
表示从u出发，往下遍历，返回u的最大价值。
dp[u][1]
表示从u出发，往下遍历，不回u的最大价值。
这样转移其实就是
dp[u][1]=max(dp[u][0]+dp[v][1]+wuv,dp[v][0]+dp[u][1]+2?wuv)
dp[u][0]=∑dp[v][0]+2?wuv
回到此题，需要求得其实是以1 ~ n为根的最大价值。
那么第一遍dfs求出上面的数组。
第二遍dfs当从u遍历v时，给v传递两个参数：
从u出发，不经过v，回到u的最大价值
从u出发，不经过v，不回u的最大价值
这样当遍历v时，考虑与
dp[v][0]
还有
dp[v][1]
组合一下，去个最大即可。
求不经过v回到u的最大价值好办，第一遍dfs的时候对路标记一下，如果经过了v，去掉v这条路上获得的最大价值即可。
但是求不经过v，不回到u的最大价值时，如果
dp[u][1]
经过v了，单单除去v这条路，又变成了回到u的最大价值。
因此考虑给dp再加一个记录，对于u而言，第一遍dfs找到回到u的最大价值和不会到u的最大以及次大价值。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int mxn = 112345;
struct Edge
{
int v,w,next,f;
};
Edge eg[mxn*2];
int head[mxn],val[mxn];
int ans[mxn];
int dp[mxn][3],nxt[mxn][3],tp;
void Add(int u,int v,int w)
{
eg[tp].v = v;
eg[tp].w = w;
eg[tp].next = head[u];
eg[tp].f = 0;
head[u] = tp++;
}
void dfs1(int u,int pre)
{
dp[u][0] = dp[u][1] = dp[u][2] = val[u];
nxt[u][0] = nxt[u][1] = nxt[u][2] = -1;
int v,w;
for(int i = head[u]; i != -1; i = eg[i].next)
{
v = eg[i].v;
if(v == pre) continue;
w = eg[i].w;
dfs1(v,u);
dp[u][1] += max(0,dp[v][0]-2*w);
dp[u][2] += max(0,dp[v][0]-2*w);
if(w <= dp[v][1])
{
int tmp = dp[u][0]+dp[v][1]-w;
if(tmp > dp[u][1])
{
if(dp[u][1] > dp[u][2])
{
dp[u][2] = dp[u][1];
nxt[u][2] = nxt[u][1];
}
dp[u][1] = tmp;
nxt[u][1] = i;
}
else if(tmp > dp[u][2])
{
dp[u][2] = tmp;
nxt[u][2] = i;
}
}
if(w*2 <= dp[v][0])
{
eg[i].f = 1;
dp[u][0] += dp[v][0]-w*2;
}
}
}
void dfs2(int u,int pre,int bk,int nbk)
{
bk = max(bk,0);
nbk = max(nbk,0);
//printf("u = %d bk = %d nbk = %dn",u,bk,nbk);
int v,w;
ans[u] = max(dp[u][0]+nbk,dp[u][1]+bk);
int nbk1,nbk2,bbk;
for(int i = head[u]; i != -1; i = eg[i].next)
{
v = eg[i].v;
w = eg[i].w;
if(v == pre) continue;
bbk = dp[u][0];
nbk1 = dp[u][1];
nbk2 = dp[u][2];
if(eg[i].f)
{
bbk = bbk-dp[v][0]+w*2;
nbk1 = nbk1-dp[v][0]+2*w;
nbk2 = nbk2-dp[v][0]+2*w;
}
if(nxt[u][1] == i)
{
nbk1 = dp[u][1]-dp[v][1]+w;
}
if(nxt[u][2] == i)
{
nbk2 = dp[u][2]-dp[v][1]+w;
}
dfs2(v,bbk-2*w+bk,max(bbk+nbk-w,bk+max(nbk1,nbk2)-w));
}
}
int main()
{
int t,n;
scanf("%d",&t);
for(int z = 1; z <= t; ++z)
{
printf("Case #%d:n",z);
memset(head,-1,sizeof(head));
tp = 0;
scanf("%d",&n);
for(int i = 1; i <= n; ++i) scanf("%d",&val[i]);
for(int i = 1; i < n; ++i)
{
scanf("%d%d%d",&u,&v,&w);
Add(u,w);
Add(v,w);
}
dfs1(1,1);
dfs2(1,1,0);
for(int i = 1; i <= n; ++i)
{
// printf("%d:n",i);
// printf("back:%dn",dp[i][0]);
// printf("nbk1:%d %dn",nxt[i][1] == -1? -1: eg[nxt[i][1]].v,dp[i][1]);
// printf("nbk2:%d %dn",nxt[i][2] == -1? -1: eg[nxt[i][2]].v,dp[i][2]);
printf("%dn",ans[i]);
}
}
return 0;
}
（编辑：核心网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
